On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
From MaRDI portal
Publication:972346
DOI10.1016/j.dam.2009.10.018zbMath1231.05096MaRDI QIDQ972346
Publication date: 25 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.10.018
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
\(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, Boolean-Width of Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Graph operations characterizing rank-width
- Distance-hereditary graphs
- Graph minors. X: Obstructions to tree-decomposition
- Edge dominating set and colorings on graphs with fixed clique-width
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- The complexity of first-order and monadic second-order logic revisited
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- Better Polynomial Algorithms on Graphs of Bounded Rank-Width
- On the Relationship Between Clique-Width and Treewidth
- Finding Branch-Decompositions and Rank-Decompositions
