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.018zbMATH Open1231.05096OpenAlexW2034183528MaRDI QIDQ972346FDOQ972346
Authors: Robert Ganian, Petr Hliněný 
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
Recommendations
- scientific article; zbMATH DE number 1107740
- scientific article; zbMATH DE number 932194
- Canonizing graphs of bounded tree width in logspace
- Canonizing Graphs of Bounded Tree Width in Logspace
- scientific article; zbMATH DE number 2086416
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Automata approach to graphs of bounded rank-width
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- On the Relationship Between Clique-Width and Treewidth
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Distance-hereditary graphs
- Rank-width and vertex-minors
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- The complexity of first-order and monadic second-order logic revisited
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Finding Branch-Decompositions and Rank-Decompositions
- Edge dominating set and colorings on graphs with fixed clique-width
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph operations characterizing rank-width
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- Better polynomial algorithms on graphs of bounded rank-width
Cited In (40)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- On the complexity of rainbow coloring problems
- Thread graphs, linear rank-width and their algorithmic applications
- Are there any good digraph width measures?
- Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth.
- Hardness transitions and uniqueness of acyclic colouring
- Courcelle's theorem -- a game-theoretic approach
- Boolean-width of graphs
- Fast FPT-approximation of branchwidth
- \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
- Slim tree-cut width
- Better polynomial algorithms on graphs of bounded rank-width
- Automata approach to graphs of bounded rank-width
- On the Boolean-width of a graph: structure and applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- Myhill-Nerode Methods for Hypergraphs
- Boolean-width of graphs
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
- Transforming graph states using single-qubit operations
- On width measures and topological problems on semi-complete digraphs
- Automata for the verification of monadic second-order graph properties
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Graph operations characterizing rank-width
- Digraph width measures in parameterized algorithmics
- Meta-kernelization with structural parameters
- Clique-width of point configurations
- Meta-kernelization using well-structured modulators
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- New results on the complexity of the Max- and Min-Rep problems
- The rank-width of edge-coloured graphs
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints
- Solving problems on graphs of high rank-width
- Solving Problems on Graphs of High Rank-Width
- Fixed-parameter tractability of treewidth and pathwidth
This page was built for publication: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972346)
