Finding augmenting chains in extensions of claw-free graphs
From MaRDI portal
Publication:1007635
DOI10.1016/S0020-0190(03)00223-0zbMath1162.68412MaRDI QIDQ1007635
Vadim V. Lozin, Alain Hertz, David Schindl
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (7)
The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On finding augmenting graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Some new hereditary classes where graph coloring remains NP-hard
Cites Work
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- Augmenting graphs for independent sets
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Computing independent sets in graphs with large girth
- Stable sets in certain \(P_6\)-free graphs
- An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
- \(P_{5}\)-free augmenting graphs and the maximum stable set problem
- Stable sets in two subclasses of banner-free graphs
- Some results on maximum stable sets in certain \(P_{5}\)-free graphs
- Stability in \(P_5\)- and banner-free graphs
- On the stable set problem in special \(P_{5}\)-free graphs
- TWO THEOREMS IN GRAPH THEORY
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Paths, Trees, and Flowers
This page was built for publication: Finding augmenting chains in extensions of claw-free graphs
