On the stable set problem in special \(P_{5}\)-free graphs
From MaRDI portal
Publication:1861559
DOI10.1016/S0166-218X(01)00321-3zbMath1028.05103OpenAlexW2059639406MaRDI QIDQ1861559
Michael U. Gerber, Vadim V. Lozin
Publication date: 9 March 2003
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00321-3
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ Struction revisited ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ Stable sets in \(k\)-colorable \(P_{5}\)-free graphs ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Partitioning Graphs into Connected Parts ⋮ Some results on graphs without long induced paths ⋮ Partitioning graphs into connected parts ⋮ Domination, coloring and stability in \(P_5\)-reducible graphs ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs
Cites Work
- Unnamed Item
- 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
- Murky graphs
- On maximal independent sets of vertices in claw-free graphs
- Stability number of bull- and chair-free graphs
- On the stability number of claw-free \(P_5\)-free and more general graphs
- Linear recognition of pseudo-split graphs
- On semi-\(P_ 4\)-sparse graphs
- On the use of Boolean methods for the computation of the stability number
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Stability in \(P_5\)- and banner-free graphs
- On (\(P_{5}\), diamond)-free graphs
- Graphs with no induced \(C_ 4\) and \(2K_ 2\)
- Polynomially solvable cases for the maximum stable set problem
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- A Linear Recognition Algorithm for Cographs
- Four classes of perfectly orderable graphs
- Quasimonotone Boolean Functions and Bistellar Graphs
- A New Algorithm for Generating All the Maximal Independent Sets
- Local transformations of graphs preserving independence number
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- An upper bound on the number of cliques in a graph
- A note on \(\alpha\)-redundant vertices in graphs
