Graph Operations Characterizing Rank-Width and Balanced Graph Expressions

DOI10.1007/978-3-540-74839-7_7zbMath1141.68523OpenAlexW1784874204MaRDI QIDQ3508555

Mamadou Moustapha Kanté, Bruno Courcelle

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, Constrained-path labellings on graphs of bounded clique-width, Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory, On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width, Graph operations characterizing rank-width, On Digraph Width Measures in Parameterized Algorithmics

Cites Work

• Unnamed Item
• Graph minors. V. Excluding a planar graph
• \(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
• The recognizability of sets of graphs is a robust property
• Graph Operations Characterizing Rank-Width and Balanced Graph Expressions
• Compact Forbidden-Set Routing
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Graph-Theoretic Concepts in Computer Science
• Finding Branch-Decompositions and Rank-Decompositions