Approximating clique-width and branch-width

2006/01/06 by Sang-il Oum, Sang‐il Oum, Paul Seymour · 9 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Block graph #Clique graph #Clique-width #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph property #Limits and Structures in Graph Theory #Line graph #Mathematics #Matroid #Pathwidth #Time complexity #Tree decomposition #Vertex (graph theory) #Voltage graph

paper · pdf · doi:10.1016/j.jctb.2005.10.006

openalex publication_date 2006/01/06 · crossref created 2006/01/06 · crossref issued 2006/07/01 · crossref published 2006/07/01 · crossref published-print 2006/07/01 · crossref deposited 2019/01/19 · openalex created_date 2025/10/10 · crossref indexed 2026/07/19 · openalex updated_date 2026/08/08

Citations

• The Tree-Width of Clique-Width Bounded Graphs without Kn,n
• Upper bounds to the clique width of graphs
• A Linear Recognition Algorithm for Cographs
• k-NLC graphs and polynomial algorithms
• Graph minors. X. Obstructions to tree-decomposition
• Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
• Graph minors. V. Excluding a planar graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Parameterized Complexity

Cited by

• Polynomial-time recognition of clique-width ≤3 graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Approximating rank-width and clique-width quickly
• Clique-Width is NP-Complete
• Intractability of Clique-Width Parameterizations
• Fast FPT-approximation of branchwidth
• Rank-width and vertex-minors
• Quantum network routing and local complementation
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Clique-width [wikipedia]