✦ LIBER ✦

Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs

✍ Scribed by Raffaele Mosca

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 588 KB
Volume: 61
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(96)00197-4

No coin nor oath required. For personal study only.

✦ Synopsis

The Maximum Stable Set Problem (MS) is a well-known NP-hard problem. A popular research stream considers classes of graphs, defined in terms of forbidden subgraphs, in which either MS is NP-hard or can be solved by polynomial algorithms. In this paper we focus on three of these classes: in one of them, MS is still NP-hard; in the others, the problem difficulty is an open question. However, for those graphs in such classes that have no induced paths with five vertices (P,), the problem becomes solvable in polynomial time. Whether MS is difficult or not in the class of P5-free graphs is still open.

📜 SIMILAR VOLUMES

P5-free augmenting graphs and the maximu

P5-free augmenting graphs and the maximum stable set problem

✍ Michael U. Gerber; Alain Hertz; David Schindl 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 174 KB

The complexity status of the maximum stable set problem in the class of P5-free graphs is unknown. In this paper, we ÿrst propose a characterization of all connected P5-free augmenting graphs. We then use this characterization to detect families of subclasses of P5-free graphs where the maximum stab