Constructive linear time algorithms for branchwidth

1997/01/01 by Hans L. Bodlaender, Dimitrios M. Thilikos · 5 citations
Computer Science · #Advanced Graph Theory Research #Algorithm #Artificial intelligence #Class (philosophy) #Complexity and Algorithms in Graphs #Computer science #Constructive #Graph #Interconnection Networks and Systems #Running time #Set (abstract data type) #Theoretical computer science #Time complexity

paper · doi:10.1007/3-540-63165-8_217

crossref issued 1997/01/01 · crossref published 1997/01/01 · crossref published-print 1997/01/01 · openalex publication_date 1997/01/01 · crossref published-online 2005/06/08 · crossref created 2012/02/26 · crossref deposited 2020/11/17 · openalex created_date 2025/10/10 · crossref indexed 2026/06/12 · openalex updated_date 2026/08/08

Citations

• Treewidth and pathwidth of permutation graphs
• Obstruction set isolation for the gate matrix layout problem
• Call routing and the ratcatcher
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A survey
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A characterization of partial 3‐trees
• Complexity of Finding Embeddings in a k-Tree
• Forbidden minors characterization of partial 3-trees
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graphs with Branchwidth at Most Three

Cited by

• Testing branch-width
• Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
• Tour Merging via Branch-Decomposition
• Fast FPT-approximation of branchwidth
• Branch-decomposition [wikipedia]