H-join decomposable graphs and algorithms with runtime single exponential in rankwidth

DOI10.1016/J.DAM.2009.09.009MaRDI QIDQ972341zbMATH OpenOpenAlexFDO

Authors Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.09.009

zbMATH Keywords

algorithmsgraphsindependent setrank-widthparameterized

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Boolean-width of graphs
• Better polynomial algorithms on graphs of bounded rank-width
• Graph-Theoretic Concepts in Computer Science
• Boolean-width of graphs
• Computing rank-width exactly

Cites work

• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A Combinatorial Decomposition Theory
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Approximating clique-width and branch-width
• Clique-width: on the price of generality
• Compositions for perfect graphs
• Decomposition of perfect graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Finding Branch-Decompositions and Rank-Decompositions
• Graph minors. X: Obstructions to tree-decomposition
• Graph operations characterizing rank-width
• Graph-Theoretic Concepts in Computer Science
• Linear time solvable optimization problems on graphs of bounded clique-width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the Relationship Between Clique-Width and Treewidth
• Partition refinement techniques: an interesting algorithmic tool kit
• Rank‐width is less than or equal to branch‐width
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• The complexity of first-order and monadic second-order logic revisited
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strong perfect graph theorem
• Three Partition Refinement Algorithms
• Transitiv orientierbare Graphen
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited in

(16)

• Star colouring of bounded degree graphs and regular graphs
• Clique-stable set separation in perfect graphs with no balanced skew-partitions
• Tree-representation of set families and applications to combinatorial decompositions
• Boolean-width of graphs
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Fast FPT-approximation of branchwidth
• On the Boolean-width of a graph: structure and applications
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Boolean-width of graphs
• One-three join: a graph operation and its consequences
• Automata for the verification of monadic second-order graph properties
• Computing \(H\)-joins with application to 2-modular decomposition
• Unifying the representation of symmetric crossing families and weakly partitive families
• Hardness transitions of star colouring and restricted star colouring
• On the complexity of finding large odd induced subgraphs and odd colorings
• The rank-width of edge-coloured graphs

This page was built for publication: \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972341)