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

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

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

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

algorithms; graphs; independent set; rank-width; parameterized

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Tree-representation of set families and applications to combinatorial decompositions, Computing \(H\)-joins with application to 2-modular decomposition, Boolean-width of graphs, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Automata for the verification of monadic second-order graph properties, The rank-width of edge-coloured graphs, Faster algorithms for vertex partitioning problems parameterized by clique-width, Unifying the representation of symmetric crossing families and weakly partitive families, On the Boolean-Width of a Graph: Structure and Applications, Boolean-Width of Graphs

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