Graph operations characterizing rank-width

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

zbMATH Keywords

clique-widthgraph operationrank-widthhierarchical decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

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

• MONA

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