On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

DOI10.1016/J.DAM.2009.10.018MaRDI QIDQ972346zbMATHOpenAlexFDO

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

zbMATH Keywords

graph colouringrank-widthparameterized algorithmMyhill-Nerode theorem

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4081531 (Why is no real title available?)
• scientific article; zbMATH DE number 475614 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 3311781 (Why is no real title available?)
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Approximating clique-width and branch-width
• Better polynomial algorithms on graphs of bounded rank-width
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Distance-hereditary graphs
• Edge dominating set and colorings on graphs with fixed clique-width
• Finding Branch-Decompositions and Rank-Decompositions
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Graph minors. X: Obstructions to tree-decomposition
• Graph operations characterizing rank-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• On the Relationship Between Clique-Width and Treewidth
• Rank-width and vertex-minors
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Upper bounds to the clique width of graphs
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth

Cited in

(38)

• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Fast FPT-approximation of branchwidth
• Thread graphs, linear rank-width and their algorithmic applications
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Courcelle's theorem -- a game-theoretic approach
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• On the Boolean-width of a graph: structure and applications
• Automata for the verification of monadic second-order graph properties
• Better polynomial algorithms on graphs of bounded rank-width
• Digraph width measures in parameterized algorithmics
• Hardness transitions and uniqueness of acyclic colouring
• Meta-kernelization using well-structured modulators
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• More applications of the \(d\)-neighbor equivalence: connectivity and acyclicity constraints
• New results on the complexity of the Max- and Min-Rep problems
• Boolean-width of graphs
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
• Meta-kernelization with structural parameters
• Multi-clique-width
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• The rank-width of edge-coloured graphs
• Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Solving problems on graphs of high rank-width
• Transforming graph states using single-qubit operations
• Are there any good digraph width measures?
• Graph operations characterizing rank-width
• Fixed-parameter tractability of treewidth and pathwidth
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• On width measures and topological problems on semi-complete digraphs
• Automata approach to graphs of bounded rank-width
• Clique-width of point configurations
• Solving problems on graphs of high rank-width
• Boolean-width of graphs
• Slim tree-cut width

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)