On the Boolean-Width of a Graph: Structure and Applications
From MaRDI portal
Publication:3057622
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
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
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
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