Geodesic
Extending the MAX Algorithm for Maximum Independent Set
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 365-386

Voir la notice de l'article provenant de la source Library of Science

The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
Keywords: maximum independent set, stable set, stability number, independence number, reduction, graph transformation, MAX Algorithm, MIN Algorithm, Vertex Order Algorithm 
@article{DMGT_2015_35_2_a13,
     author = {L\^e, Ngoc C. and Brause, Christoph and Schiermeyer, Ingo},
     title = {Extending the {MAX} {Algorithm} for {Maximum} {Independent} {Set}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {365--386},
     publisher = {mathdoc},
     volume = {35},
     number = {2},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/}
}
TY  - JOUR
AU  - Lê, Ngoc C.
AU  - Brause, Christoph
AU  - Schiermeyer, Ingo
TI  - Extending the MAX Algorithm for Maximum Independent Set
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 365
EP  - 386
VL  - 35
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/
LA  - en
ID  - DMGT_2015_35_2_a13
ER  - 
%0 Journal Article
%A Lê, Ngoc C.
%A Brause, Christoph
%A Schiermeyer, Ingo
%T Extending the MAX Algorithm for Maximum Independent Set
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 365-386
%V 35
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/
%G en
%F DMGT_2015_35_2_a13
Lê, Ngoc C.; Brause, Christoph; Schiermeyer, Ingo. Extending the MAX Algorithm for Maximum Independent Set. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 2, pp. 365-386. http://geodesic.mathdoc.fr/item/DMGT_2015_35_2_a13/