Boolean-width of graphs
From MaRDI portal
Publication:719257
DOI10.1016/j.tcs.2011.05.022zbMath1225.68133OpenAlexW2154682992MaRDI QIDQ719257
Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle
Publication date: 10 October 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.05.022
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (34)
Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Between treewidth and clique-width ⋮ Rank-width: algorithmic and structural results ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ Between Treewidth and Clique-Width ⋮ From tree-decompositions to clique-width terms ⋮ A SAT Approach to Clique-Width ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Meta-kernelization with structural parameters ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Computing partial hypergraphs of bounded width ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis ⋮ Linear Clique‐Width for Hereditary Classes of Cographs ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Computing \(H\)-joins with application to 2-modular decomposition ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ On low rank-width colorings ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ On the star forest polytope for trees and cycles ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Efficient parallel algorithms for parameterized problems ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Unnamed Item ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for treewidth
- Row space cardinalities
- 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
- Clique-width of graphs defined by one-vertex extensions
- 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
- Linear time solvable optimization problems on graphs of bounded clique-width
- Handle-rewriting hypergraph grammars
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Finding Good Decompositions for Dynamic Programming on Dense Graphs
- Rank-width of random graphs
- On the Boolean-Width of a Graph: Structure and Applications
- Graph Classes with Structured Neighborhoods and Algorithmic Applications
- The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
- Faster Algorithms on Branch and Clique Decompositions
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Feedback Vertex Set on Graphs of Low Cliquewidth
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- The Rank-Width of the Square Grid
- On the Relationship Between Clique-Width and Treewidth
- Rank‐width is less than or equal to branch‐width
- Graph-Theoretic Concepts in Computer Science
- Finding Branch-Decompositions and Rank-Decompositions
This page was built for publication: Boolean-width of graphs
