Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
DOI10.1016/S0196-6774(03)00046-4zbMATH Open1079.68108OpenAlexW2118169763MaRDI QIDQ4458873FDOQ4458873
Authors: 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
Recommendations
- New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
- Single-source shortest-paths on arbitrary directed graphs in linear average-case time
- Simpler computation of single-source shortest paths in linear average time
- STACS 2004
- scientific article; zbMATH DE number 1416161
threshold approachBellman-Ford algorithm\(\Delta\)-stepping algorithmapproximate Bucket implementationgraphs with random edge weightsPallottino's incremental graph algorithmtopological ordering SSSP algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)
Cited In (8)
- A Forward-Backward Single-Source Shortest Paths Algorithm
- STACS 2004
- Title not available (Why is that?)
- Title not available (Why is that?)
- Via Detours to I/O-Efficient Shortest Paths
- New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
- Simpler computation of single-source shortest paths in linear average time
- Single-source shortest-paths on arbitrary directed graphs in linear average-case time
This page was built for publication: Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458873)
