𝔖 Bobbio Scriptorium
✦   LIBER   ✦

P5-free augmenting graphs and the maximum stable set problem

✍ Scribed by Michael U. Gerber; Alain Hertz; David Schindl

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
174 KB
Volume
132
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 stable set problem has a polynomial time solution. These families extend several previously studied classes.

πŸ“œ SIMILAR VOLUMES

An augmenting graph approach to the stab
An augmenting graph approach to the stable set problem in P5-free graphs
✍ Rodica Boliac; Vadim V. Lozin πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 149 KB

The complexity status of the stable set problem in the class of P5-free graphs is unknown. In the present paper we study an approach to the problem based on ΓΏnding augmenting graphs. The main result is that the stable set problem in the class of P5-free graphs is polynomially equivalent to the prob

Polynomial algorithms for the maximum st
Polynomial algorithms for the maximum stable set problem on particular classes of P5-free graphs
✍ Raffaele Mosca πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 588 KB

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 th