Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds

DOI10.1016/S0196-6774(03)00046-4zbMath1079.68108OpenAlexW2118169763MaRDI QIDQ4458873

Ulrich Meyer

Publication date: 14 March 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00046-4

zbMATH Keywords

threshold approachBellman-Ford algorithm\(\Delta\)-stepping algorithmapproximate Bucket implementationgraphs with random edge weightsPallottino's incremental graph algorithmtopological ordering SSSP algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Via Detours to I/O-Efficient Shortest Paths ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm

This page was built for publication: Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds