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

DOI10.1016/j.dam.2009.09.009zbMath1216.05153OpenAlexW1977262817MaRDI QIDQ972341

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

zbMATH Keywords

algorithmsgraphsindependent setrank-widthparameterized

Mathematics Subject Classification ID

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

Related Items (13)

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ The rank-width of edge-coloured graphs ⋮ Tree-representation of set families and applications to combinatorial decompositions ⋮ Automata for the verification of monadic second-order graph properties ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Computing \(H\)-joins with application to 2-modular decomposition ⋮ On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Boolean-Width of Graphs ⋮ Unifying the representation of symmetric crossing families and weakly partitive families

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• 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
• Graph operations characterizing rank-width
• Decomposition of perfect graphs
• Graph minors. X: Obstructions to tree-decomposition
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• The complexity of first-order and monadic second-order logic revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Compositions for perfect graphs
• Approximating clique-width and branch-width
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• Three Partition Refinement Algorithms
• A Combinatorial Decomposition Theory
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
• On the Relationship Between Clique-Width and Treewidth
• Rank‐width is less than or equal to branch‐width
• Transitiv orientierbare Graphen
• Graph-Theoretic Concepts in Computer Science
• Finding Branch-Decompositions and Rank-Decompositions

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