Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

2000/03/04 by B. Courcelle, Johann A. Makowsky, J. A. Makowsky +2 · 12 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Measure (data warehouse) #Pathwidth #Time complexity #Tree (set theory) #Treewidth

paper · doi:10.1007/s002249910009

crossref issued 2000/03/04 · crossref published 2000/03/04 · crossref published-print 2000/03/04 · openalex publication_date 2000/03/04 · crossref created 2002/08/25 · crossref deposited 2019/05/24 · openalex created_date 2025/10/10 · crossref indexed 2026/08/01 · openalex updated_date 2026/08/03

Citations

• Upper bounds to the clique width of graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth

Cited by

• Deciding first-order properties of locally tree-decomposable structures
• On merge-models
• Line graphs of bounded clique-width
• Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
• FO Value Discovery and Partial Vertex Cover Discovery
• Computing the Tutte Polynomial on Graphs of Bounded Clique-Width
• Twin-width VIIIa: Delineation
• Branch-depth: Generalizing tree-depth of graphs
• Independent Set on P_k-Free Graphs in Quasi-Polynomial Time
• Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer
• The Behavior of Clique-Width under Graph Operations and Graph Transformations
• Cograph [wikipedia]