Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
Authors:
- Siamak TazariSTSiamak Tazari
- Matthias Müller-HannemannMMMatthias Müller-Hannemann
- 28 February 2009
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 157 (4) , 673-684
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- A Shortest Path Algorithm for Real-Weighted Undirected GraphsSIAM Journal on Computing, 2005
- Undirected single-source shortest paths with positive integer weights in linear timeJournal of the ACM, 1999
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- A separator theorem for nonplanar graphsJournal of the American Mathematical Society, 1990
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- A note on two problems in connexion with graphsNumerische Mathematik, 1959