Graph Operations Characterizing Rank-Width and Balanced Graph Expressions

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

Bruno Courcelle, Mamadou Moustapha Kanté

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

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Graph operations characterizing rank-width, Graph Operations Characterizing Rank-Width and Balanced Graph Expressions, 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