k-NLC graphs and polynomial algorithms

1994/10/01 by Egon Wanke · 101 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Block graph #Chordal graph #Cograph #Combinatorics #Comparability graph #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Pathwidth

paper · pdf · doi:10.1016/0166-218x(94)90026-4

published in Discrete Applied Mathematics 54(2-3), 251-266 (Elsevier BV)

crossref issued 1994/10/01 · crossref published 1994/10/01 · crossref published-print 1994/10/01 · openalex publication_date 1994/10/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/07/15 · openalex updated_date 2026/08/02

Citations

• Linear-time computation of optimal subgraphs of decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• Dynamic programming on graphs with bounded treewidth
• Dacey Graphs

Cited by

• Approximating clique-width and branch-width
• Polynomial-time recognition of clique-width ≤3 graphs
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• On the Relationship Between Clique-Width and Treewidth
• 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
• How to Solve NP-hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time
• Characterizations for co-graphs defined by restricted NLC-width or clique-width operations
• Clique-width [wikipedia]