Groupe d’études et de recherche en analyse des décisions

G-2004-39

The Maximum Independent Set Problem and Augmenting Graphs

et

In the present paper we review the method of augmenting graphs, which is a general approach to solve the maximum independent set problem. Our objective is the employment of this approach to develop polynomial-time algorithms for the problem on special classes of graphs. We report principal results in this area and propose several new contributions to the topic.

, 29 pages