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.05096OpenAlexW2034183528MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (34)
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ Solving Problems on Graphs of High Rank-Width ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ On the complexity of rainbow coloring problems ⋮ The rank-width of edge-coloured graphs ⋮ Transforming graph states using single-qubit operations ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Meta-kernelization using well-structured modulators ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Are there any good digraph width measures? ⋮ Meta-kernelization with structural parameters ⋮ Hardness transitions and uniqueness of acyclic colouring ⋮ Automata for the verification of monadic second-order graph properties ⋮ Solving problems on graphs of high rank-width ⋮ Digraph width measures in parameterized algorithmics ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Thread Graphs, Linear Rank-Width and Their Algorithmic Applications ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ Unnamed Item ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ Clique-width of point configurations ⋮ Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Boolean-Width of Graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Unnamed Item ⋮ Myhill-Nerode Methods for Hypergraphs
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
This page was built for publication: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
