On algorithms for (\(P_5\), gem)-free graphs

DOI10.1016/j.tcs.2005.09.026zbMath1086.68050OpenAlexW2015452703WikidataQ59567840 ScholiaQ59567840MaRDI QIDQ817767

Michaël Rao, Dieter Kratsch, Hans L. Bodlaender, 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

zbMATH Keywords

independent setcliquecoloringrecognition algorithmsmodular decompositionclique cover(\(P_{5}\), gem)-free graphs

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

One-three join: a graph operation and its consequences, Weighted independent sets in classes of \(P_6\)-free graphs, Hierarchical and modularly-minimal vertex colorings, 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, More results on weighted independent domination, 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, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, 2-clique-bond of stable set polyhedra, Dominating induced matchings for \(P_7\)-free graphs in linear time, Polynomial cases for the vertex coloring problem, Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs, Solving some NP-complete problems using split decomposition, Independent domination in finitely defined classes of graphs: polynomial algorithms

Cites Work

• The strong perfect graph theorem
• Complement reducible graphs
• Trivially perfect graphs
• Modular decomposition and transitive orientation
• \(k\)-NLC graphs and polynomial algorithms
• Generalized coloring for tree-like graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Computing the treewidth and the minimum fill-in with the modular decomposition
• On the structure of (\(P_{5}\),\,gem)-free graphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Achromatic number is NP-complete for cographs and interval graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Normal hypergraphs and the perfect graph conjecture
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• Easy problems for tree-decomposable graphs
• A Linear Recognition Algorithm for Cographs
• The Comparability Graph of a Tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Channel assignment and weighted coloring
• A Note on "The Comparability Graph of a Tree"
• Transitiv orientierbare Graphen
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item