Via Detours to I/O-Efficient Shortest Paths

DOI10.1007/978-3-642-03456-5_15zbMath1258.68105OpenAlexW1697432253MaRDI QIDQ3644724

Ulrich Meyer

Publication date: 12 November 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03456-5_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• STXXL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A functional approach to external graph algorithms
• Simpler computation of single-source shortest paths in linear average time
• Cache-Oblivious Algorithms
• On Trade-Offs in External-Memory Diameter-Approximation
• A Practical Shortest Path Algorithm with Linear Expected Time
• A computational study of external-memory BFS algorithms
• I/O-Efficient Planar Separators
• Parallel Algorithms for Depth-First Searches I. Planar Graphs
• A Separator Theorem for Planar Graphs
• On External-Memory Planar Depth First Search
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Δ-stepping: a parallelizable shortest path algorithm
• Algorithms and Experiments for the Webgraph
• Algorithm Theory - SWAT 2004
• Fast computation of empirically tight bounds for the diameter of massive graphs
• I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths
• Automata, Languages and Programming
• Algorithms - ESA 2003
• I/O-Efficient Algorithms on Near-Planar Graphs