On the Boolean-Width of a Graph: Structure and Applications

DOI10.1007/978-3-642-16926-7_16zbMath1310.05193OpenAlexW1881512968MaRDI QIDQ3057622

Martin Vatshelle, Jan Arne Telle, Yuri Rabinovich, Gabriel Renault, Binh-Minh Bui-Xuan, Isolde Adler

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ The rank-width of edge-coloured graphs ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Parameterized complexity of generalized domination problems ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ A SAT Approach to Branchwidth ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications

Uses Software

• ComputeTW

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Edge dominating set and colorings on graphs with fixed clique-width
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Vertex-minor reductions can simulate edge contractions
• Rank-width of random graphs
• On the Boolean-Width of a Graph: Structure and Applications
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Boolean-Width of Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• On the Relationship Between Clique-Width and Treewidth
• Dynamic Programming and Fast Matrix Multiplication
• Rank‐width is less than or equal to branch‐width

This page was built for publication: On the Boolean-Width of a Graph: Structure and Applications