Retour

G-2004-39

The Maximum Independent Set Problem and Augmenting Graphs

et

référence BibTeX

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

Axe de recherche

Publication

The maximum independent set problem and augmenting graphs
et
Eds Avis, D, Hertz, A & Marcotte, O, Graph Theory and Combinatorial Optimization, (4), Springer, 2005 référence BibTeX