Linear-time computation of optimal subgraphs of decomposable graphs

1987/06/01 by Marshall Bern, M.W Bern, Eugene L. Lawler +3 · 10 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph Theory and Algorithms #Matching (statistics) #Mathematics #Time complexity #Travelling salesman problem

paper · doi:10.1016/0196-6774(87)90039-3

crossref issued 1987/06/01 · crossref published 1987/06/01 · crossref published-print 1987/06/01 · openalex publication_date 1987/06/01 · crossref created 2004/11/06 · openalex created_date 2025/10/10 · crossref deposited 2026/04/30 · crossref indexed 2026/05/04 · openalex updated_date 2026/07/30

Cited by

• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Linear time algorithms for NP-hard problems restricted to partial k-trees
• LP approximations to mixed-integer polynomial optimization problems
• Diameter and Treewidth in Minor-Closed Graph Families
• A partial k-arboretum of graphs with bounded treewidth
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Efficient Subgraph Matching
• Tree decomposition [wikipedia]
• Treewidth [wikipedia]