An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
From MaRDI portal
Publication:1414237
DOI10.1016/S0166-218X(03)00221-XzbMath1026.05098OpenAlexW1989632159MaRDI QIDQ1414237
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
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
