On the Boolean-width of a graph: structure and applications

DOI10.1007/978-3-642-16926-7_16MaRDI QIDQ3057622zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Boolean-width of graphs
• Boolean-width of graphs
• Graph classes with structured neighborhoods and algorithmic applications
• Upper Bounds on Boolean-Width with Applications to Exact Algorithms
• Practical algorithms for linear Boolean-width

Cites work

• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Boolean-width of graphs
• Dynamic Programming and Fast Matrix Multiplication
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Edge dominating set and colorings on graphs with fixed clique-width
• scientific article; zbMATH DE number 3779513 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On the Boolean-width of a graph: structure and applications
• On the Relationship Between Clique-Width and Treewidth
• Rank-width of random graphs
• Rank‐width is less than or equal to branch‐width
• Treewidth computations. I: Upper bounds
• Vertex-minor reductions can simulate edge contractions

Cited in

(17)

• Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
• On the capacity of Boolean graph formulæ
• C-planarity testing of embedded clustered graphs with bounded dual carving-width
• On width measures and topological problems on semi-complete digraphs
• 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
• Boolean-width of graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Parameterized complexity of generalized domination problems
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• Practical algorithms for linear Boolean-width
• Sparse graphs of twin-width 2 have bounded tree-width
• Boolean-width of graphs
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs

Describes a project that uses

Uses Software

• ComputeTW

This page was built for publication: On the Boolean-width of a graph: structure and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057622)