Call routing and the ratcatcher

1994/06/01 by Paul Seymour, P. D. Seymour, Robin Thomas +1 · 13 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer network #Computer science #Discrete mathematics #Graph #Mathematics #Mobile Ad Hoc Networks #Planar #Planar graph #Routing (electronic design automation) #Steiner tree problem #Tree (set theory) #Valency #Vertex (graph theory)

paper · doi:10.1007/bf01215352

crossref issued 1994/06/01 · crossref published 1994/06/01 · crossref published-print 1994/06/01 · openalex publication_date 1994/06/01 · crossref created 2005/02/25 · crossref deposited 2019/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/19 · crossref indexed 2026/06/29

Citations

• Some simplified NP-complete graph problems
• Some simplified NP-complete problems
• Quickly excluding a forest

Cited by

• Constructive linear time algorithms for branchwidth
• The branchwidth of graphs and their cycle matroids
• Computing branchwidth via efficient triangulations and blocks
• Finding Branch-Decompositions and Rank-Decompositions
• Approximating rank-width and clique-width quickly
• Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
• Tour Merging via Branch-Decomposition
• Fast FPT-approximation of branchwidth
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• New upper bounds on the decomposability of planar graphs
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions
• Branch-decomposition [wikipedia]
• Planar separator theorem [wikipedia]