Structure and stability number of chair-, co-P- and gem-free graphs revisited
From MaRDI portal
Publication:1007592
DOI10.1016/S0020-0190(02)00487-8zbMath1173.68597OpenAlexW1965968140MaRDI QIDQ1007592
Hoàng-Oanh Le, Jean-Marie Vanherpe, Andreas Brandstädt
Publication date: 23 March 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00487-8
graph algorithmsmodular decompositionmaximum weight stable setprime graphs(chairclique width of graphsco-Pgem)-free graphs
Related Items
New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ On the approximability of the maximum induced matching problem ⋮ The stable set polytope for some extensions of \(P_4\)-free graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complement reducible graphs
- Modular decomposition and transitive orientation
- On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
- Conic reduction of graphs for the stable set problem
- Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Handle-rewriting hypergraph grammars
- Efficient and Practical Algorithms for Sequential Modular Decomposition
- A Linear Recognition Algorithm for Cographs
- Some classes of perfectly orderable graphs
- Graph Classes: A Survey
