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.
@article{bwmeta1.element.doi-10_7151_dmgt_1965,
author = {Ngoc C. L\^e and Christoph Brause and Ingo Schiermeyer},
title = {On Sequential Heuristic Methods for the Maximum Independent Set Problem},
journal = {Discussiones Mathematicae Graph Theory},
volume = {37},
year = {2017},
pages = {415-426},
zbl = {06705137},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1965}
}
Ngoc C. Lê; Christoph Brause; Ingo Schiermeyer. On Sequential Heuristic Methods for the Maximum Independent Set Problem. Discussiones Mathematicae Graph Theory, Tome 37 (2017) pp. 415-426. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1965/