A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes

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

zbMATH Keywords

shortest paths algorithms

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68W05: Nonnumerical algorithms

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Single source shortest paths in \(H\)-minor free graphs

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