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

DOI10.1016/J.DAM.2009.09.009zbMATH Open1216.05153OpenAlexW1977262817MaRDI QIDQ972341FDOQ972341

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

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

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

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)

Cites Work

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

Cited In (14)

• 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
• Fast FPT-approximation of branchwidth
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Boolean-width of graphs
• Automata for the verification of monadic second-order graph properties
• On the Boolean-Width of a Graph: Structure and Applications
• Unifying the representation of symmetric crossing families and weakly partitive families
• Computing \(H\)-joins with application to 2-modular decomposition
• 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)