On algorithms for (P₅, gem)-free graphs
DOI10.1016/J.TCS.2005.09.026zbMATH Open1086.68050OpenAlexW2015452703WikidataQ59567840 ScholiaQ59567840MaRDI QIDQ817767FDOQ817767
Authors: Hans L. Bodlaender, Dieter Kratsch, Michaël Rao, Andreas Brandstädt, Jeremy P. Spinrad 
Publication date: 20 March 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.026
Recommendations
modular decompositioncliqueindependent setcoloringrecognition algorithmsclique cover(\(P_{5}\), gem)-free graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Normal hypergraphs and the perfect graph conjecture
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Complement reducible graphs
- Modular decomposition and transitive orientation
- Linear time solvable optimization problems on graphs of bounded clique-width
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- The strong perfect graph theorem
- Trivially perfect graphs
- The Comparability Graph of a Tree
- Transitiv orientierbare Graphen
- Algorithmic Aspects of Vertex Elimination on Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear Recognition Algorithm for Cographs
- Channel assignment and weighted coloring
- Title not available (Why is that?)
- Generalized coloring for tree-like graphs
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Achromatic number is NP-complete for cographs and interval graphs
- A Note on "The Comparability Graph of a Tree"
- \(k\)-NLC graphs and polynomial algorithms
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- A translation of Gallai's paper: `Transitiv orientierbare Graphen'
- Title not available (Why is that?)
- Efficient and practical algorithms for sequential modular decomposition
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Title not available (Why is that?)
Cited In (23)
- Title not available (Why is that?)
- A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- One-three join: a graph operation and its consequences
- New applications of clique separator decomposition for the maximum weight stable set problem
- Solving some NP-complete problems using split decomposition
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- 2-clique-bond of stable set polyhedra
- On (\(P_{5}\), diamond)-free graphs
- Finding a sun in building-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs
- More results on weighted independent domination
- Hierarchical and modularly-minimal vertex colorings
- Polynomial cases for the vertex coloring problem
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Fundamentals of Computation Theory
This page was built for publication: On algorithms for (\(P_5\), gem)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817767)
