Boolean-Width of Graphs

DOI10.1007/978-3-642-11269-0_5zbMath1273.68273OpenAlexW2175446664MaRDI QIDQ3656851

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

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_5

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Tree-representation of set families and applications to combinatorial decompositions ⋮ Unnamed Item ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications

Cites Work

• Unnamed Item
• Unnamed Item
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Treewidth computations. I: Upper bounds
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Decomposition of perfect graphs
• Graph minors. X: Obstructions to tree-decomposition
• Branch-width and well-quasi-ordering in matroids and graphs.
• Edge dominating set and colorings on graphs with fixed clique-width
• Approximating clique-width and branch-width
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• The Rank-Width of the Square Grid
• On the Relationship Between Clique-Width and Treewidth
• Dynamic Programming and Fast Matrix Multiplication
• Rank‐width is less than or equal to branch‐width
• Graph-Theoretic Concepts in Computer Science
• Finding Branch-Decompositions and Rank-Decompositions