An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs

DOI10.1016/S0166-218X(03)00221-XzbMath1026.05098OpenAlexW1989632159MaRDI QIDQ1414237

R. Boliac, Vadim V. Lozin

Publication date: 20 November 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00221-x

zbMATH Keywords

stable setpolynomial algorithmaugmenting graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ On finding augmenting graphs ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Finding augmenting chains in extensions of claw-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• The complexity of generalized clique packing
• The strong perfect graph conjecture for pan-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stability number of bull- and chair-free graphs
• Some simplified NP-complete graph problems
• On minimal imperfect graphs without induced \(P_5\)
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stable sets in certain \(P_6\)-free graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Stability in \(P_5\)- and banner-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• A Linear Recognition Algorithm for Cographs
• Polynomial algorithm for finding the largest independent sets in graphs without forks

This page was built for publication: An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs