A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
From MaRDI portal
Publication:5302069
DOI10.1007/978-3-540-92248-3_32zbMath1202.05141WikidataQ57013253 ScholiaQ57013253MaRDI QIDQ5302069
Siamak Tazari, Matthias Müller-Hannemann
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_32
05C35: Extremal problems in graph theory
68W05: Nonnumerical algorithms
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Cites Work
- 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
- 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
- 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
- Une heuristique pour le problème de l'arbre de Steiner
- 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