Geodesic
On Sequential Heuristic Methods for the Maximum Independent Set Problem
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 415-426

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

We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6], are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.
Keywords: maximum independent set, heuristic, MIN, MAX, VO, vertex ordering 
@article{DMGT_2017_37_2_a7,
     author = {L\^e, Ngoc C. and Brause, Christoph and Schiermeyer, Ingo},
     title = {On {Sequential} {Heuristic} {Methods} for the {Maximum} {Independent} {Set} {Problem}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {415--426},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a7/}
}
TY  - JOUR
AU  - Lê, Ngoc C.
AU  - Brause, Christoph
AU  - Schiermeyer, Ingo
TI  - On Sequential Heuristic Methods for the Maximum Independent Set Problem
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 415
EP  - 426
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a7/
LA  - en
ID  - DMGT_2017_37_2_a7
ER  - 
%0 Journal Article
%A Lê, Ngoc C.
%A Brause, Christoph
%A Schiermeyer, Ingo
%T On Sequential Heuristic Methods for the Maximum Independent Set Problem
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 415-426
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a7/
%G en
%F DMGT_2017_37_2_a7
Lê, Ngoc C.; Brause, Christoph; Schiermeyer, Ingo. On Sequential Heuristic Methods for the Maximum Independent Set Problem. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 415-426. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a7/