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

DOI10.1007/978-3-642-16926-7_16zbMath1310.05193MaRDI 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

68Q25: Analysis of algorithms and problem complexity

05C80: Random graphs (graph-theoretic aspects)

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Parameterized complexity of generalized domination problems, Boolean-width of graphs, Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis, The rank-width of edge-coloured graphs, A SAT Approach to Branchwidth, Finding Good Decompositions for Dynamic Programming on Dense Graphs, On the Boolean-Width of a Graph: Structure and Applications, 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