Graph operations characterizing rank-width
From MaRDI portal
Publication:1028455
DOI10.1016/j.dam.2008.08.026zbMath1173.05349OpenAlexW2011632049MaRDI QIDQ1028455
Mamadou Moustapha Kanté, Bruno Courcelle
Publication date: 30 June 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.026
Related Items (11)
The rank-width of edge-coloured graphs ⋮ Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs ⋮ Grammars and clique-width bounds from split decompositions ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Well-quasi-ordering of matrices under Schur complement and applications to directed graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ On the approximate compressibility of connected vertex cover ⋮ \(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 ⋮ A characterisation of clique-width through nested partitions
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithmic uses of the Feferman-Vaught theorem
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- The monadic second-order logic of graphs. VII: Graphs as relational structures
- \(k\)-NLC graphs and polynomial algorithms
- Query efficient implementation of graphs of bounded clique-width
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Vertex-minor reductions can simulate edge contractions
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- Recognizability, hypergraph operations, and logical types
- Rank-width and vertex-minors
- The recognizability of sets of graphs is a robust property
- The relative clique-width of a graph
- Clique-width minimization is NP-hard
- Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
- Compact Forbidden-Set Routing
- Deciding Clique-Width for Graphs of Bounded Tree-Width
- On the Relationship Between Clique-Width and Treewidth
- Rank‐width is less than or equal to branch‐width
- Finding Branch-Decompositions and Rank-Decompositions
This page was built for publication: Graph operations characterizing rank-width
