𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On stable set polyhedra for K1,3-free graphs

✍ Scribed by Rick Giles; L.E Trotter Jr.

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
700 KB
Volume
31
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ 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

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

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