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/

[1] V.E. Alekseev and V.V. Lozin, Augmenting graphs for independent sets, Discrete Appl. Math. 145 (2004) 3-10. doi: 10.1016/j.dam.2003.09.003

[2] P. Borowiecki, F. Göring, J. Harant and D. Rautenbach, The potential of greed for independence, J. Graph Theory 71 (2012) 245-259. doi: 10.1002/jgt.20644

[3] A. Brandstädt and V.V. Lozin, A note on -redundant vertices in graphs, Discrete Appl. Math. 108 (2001) 301-308. doi: 10.1016/S0166-218X(00)00239-0

[4] Y. Caro, New results on the independence, Technical Report, Tel-Aviv University (1979).

[5] M.U. Gerber and V.V. Lozin, On the stable set problem in special P5-free graphs, Discrete Appl. Math. 125 (2003) 215-224. doi: 10.1016/S0166-218X(01)00321-3

[6] J.R. Griggs, Lower bounds on the independence number in terms of the degrees, J. Combin. Theory Ser. B 34 (1983) 22-39. doi: 10.1016/0095-8956(83)90003-5

[7] J. Harant, Z. Ryjáček and I. Schiermeyer, Forbidden subgraphs and MIN-algorithm for independence number, Discrete Math. 256 (2002) 193-201. doi: 10.1016/S0012-365X(02)00571-X

[8] N.C. Lê, C. Brause and I. Schiermeyer, New sufficient conditions for -redundant vertices, Discrete Math. 338 (2015) 1674-1680. doi: 10.1016/j.disc.2014.07.002

[9] N.C. Lê, C. Brause and I. Schiermeyer, Extending the Max Algorithm for maximum independent set, Discuss. Math. Graph Theory 35 (2015) 365-386. doi: 10.7151/dmgt.1811

[10] V.V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Inform. Process. Lett. 88 (2003) 167-171. doi: 10.1016/j.ipl.2003.07.004

[11] N.V.R. Mahadev and B.A. Reed, A note on vertex orders for stability number, J. Graph Theory 30 (1999) 113-120. doi: 10.1002/(SICI)1097-0118(199902)30:2h113::AID-JGT5i3.0.CO;2-#

[12] O. Murphy, Lower bounds on the stability number of graphs computed in terms of degrees, Discrete Math. 90 (1991) 207-211. doi: 10.1016/0012-365X(91)90357-8

[13] D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination of graphs, SIAM J. Comput. 5 (1976) 266-283. doi: 10.1137/0205021

[14] V.K. Wei, A lower bound on the stability number of a simple graph, Technical Report, Bell Laboratories (1981).

[15] I.E. Zverovich, Minimum degree algorithms for stability number, Discrete Appl. Math. 132 (2004) 211-216. doi: 10.1016/S0166-218X(03)00402-5