On Sequential Heuristic Methods for the Maximum Independent Set Problem

• Autorzy: Ngoc C. Lê , Christoph Brause , Ingo Schiermeyer
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

maximum independent set; heuristic; MIN; MAX; VO; vertex ordering

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 415-426

Daty

wydano

2017-05-01

otrzymano

2015-12-29

poprawiono

2017-02-01

zaakceptowano

2017-02-01

online

2017-04-01

Twórcy

autor

Ngoc C. Lê

• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg School of Applied Mathematics and Informatics Hanoi University of Science and Technology,

autor

Christoph Brause

• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg,

autor

Ingo Schiermeyer

• Faculty of Mathematics and Computer Science Technische Universität Bergakademie Freiberg,

Identyfikatory

DOI

10.7151/dmgt.1965