On Sequential Heuristic Methods for the Maximum Independent Set Problem

Ngoc C. Lê, Christoph Brause, and Ingo Schiermeyer. "On Sequential Heuristic Methods for the Maximum Independent Set Problem." Discussiones Mathematicae Graph Theory 37.2 (2017): 415-426. <http://eudml.org/doc/288057>.

@article{NgocC2017,
abstract = {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.},
author = {Ngoc C. Lê, Christoph Brause, Ingo Schiermeyer},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {maximum independent set; heuristic; MIN; MAX; VO; vertex ordering},
language = {eng},
number = {2},
pages = {415-426},
title = {On Sequential Heuristic Methods for the Maximum Independent Set Problem},
url = {http://eudml.org/doc/288057},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Ngoc C. Lê
AU - Christoph Brause
AU - Ingo Schiermeyer
TI - On Sequential Heuristic Methods for the Maximum Independent Set Problem
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 415
EP - 426
AB - 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.
LA - eng
KW - maximum independent set; heuristic; MIN; MAX; VO; vertex ordering
UR - http://eudml.org/doc/288057
ER -