Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation

2008/09/08 by Siamak Tazari, Matthias Müller‐Hannemann, Matthias Müller-Hannemann · 18 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Block graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Line graph #Mathematics #Minor (academic) #Pathwidth #Planar graph #Steiner tree problem #Time complexity

paper · doi:10.1016/j.dam.2008.08.002

published in Discrete Applied Mathematics 157(4), 673-684 (Elsevier BV)

openalex publication_date 2008/09/08 · crossref created 2008/09/08 · crossref issued 2009/02/01 · crossref published 2009/02/01 · crossref published-print 2009/02/01 · crossref deposited 2018/12/25 · crossref indexed 2024/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Citations

• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• The Rectilinear Steiner Tree Problem is NP-Complete
• Graph Minors. XVI. Excluding a non-planar graph
• A Separator Theorem for Planar Graphs
• Graph Minors. XX. Wagner's conjecture
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding Minimum Spanning Trees
• A separator theorem for nonplanar graphs
• A note on two problems in connexion with graphs
• Reducibility among Combinatorial Problems
• Faster Shortest-Path Algorithms for Planar Graphs

Cited by

• Planar separator theorem [wikipedia]