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.
Paru en mai 2004 , 29 pages
Axe de recherche
Publication
jan. 2005
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