Linear time algorithms for NP-hard problems restricted to partial k-trees

1989/04/01 by Stefan Arnborg, Andrzej Proskurowski · 19 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Hamiltonian path #Hamiltonian path problem #Interconnection Networks and Systems #Mathematics #Time complexity

paper · doi:10.1016/0166-218x(89)90031-0

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

Citations

• Linear-time computation of optimal subgraphs of decomposable graphs
• Complement reducible graphs
• Complexity of Finding Embeddings in a k-Tree

Cited by

• Finding approximate separators and computing tree width quickly
• A Single-Exponential Time 2-Approximation Algorithm for Treewidth
• The Structure and Number of Obstructions to Treewidth
• All Structured Programs Have Small Tree Width and Good Register Allocation
• Directed Tree-Width
• Approximating treewidth and pathwidth of some classes of perfect graphs
• Computing treewidth and minimum fill-in: All you need are the minimal separators
• Treewidth and pathwidth of permutation graphs
• A simple linear-time algorithm for finding path-decompositions of small width
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• The Graph Minor Algorithm with Parity Conditions
• Graph minor theory
• Kernelization: Theory of Parameterized Preprocessing
• Two strikes against perfect phylogeny
• Computing directed path-width and directed tree-width of recursively defined digraphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Layout of Graphs with Bounded Tree-Width
• Tree decomposition [wikipedia]
• Treewidth [wikipedia]