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

DOI10.1016/j.dam.2008.08.002zbMath1173.05329OpenAlexW2064175146WikidataQ57013249 ScholiaQ57013249MaRDI QIDQ1028460

Siamak Tazari, Matthias Müller-Hannemann

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.002

zbMATH Keywords

shortest pathplanar graphSteiner treeMehlhorn's algorithmminor-closed graph classes

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

Related Items (9)

Minimum Cuts in Surface Graphs ⋮ Cliques in graphs excluding a complete graph minor ⋮ A simple algorithm for replacement paths problem ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Counting and sampling minimum cuts in genus \(g\) graphs ⋮ Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs ⋮ Accelerated Bend Minimization ⋮ Many distances in planar graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Graph minors. XX: Wagner's conjecture
• The Steiner problem with edge lengths 1 and 2
• Graph minors. XVI: Excluding a non-planar graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Undirected single-source shortest paths with positive integer weights in linear time
• Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Finding Minimum Spanning Trees
• Une heuristique pour le problème de l'arbre de Steiner
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Fibonacci heaps and their uses in improved network optimization algorithms
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• A faster approximation algorithm for the Steiner problem in graphs
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation