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

DOI10.1016/S0196-6774(03)00046-4MaRDI QIDQ4458873zbMATH OpenOpenAlexFDO

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

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

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)

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

Cited in

(9)

• STACS 2004
• Via Detours to I/O-Efficient Shortest Paths
• scientific article; zbMATH DE number 1416161 (Why is no real title available?)
• New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
• A forward-backward single-source shortest paths algorithm
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• scientific article; zbMATH DE number 1535253 (Why is no real title available?)
• Simpler computation of single-source shortest paths in linear average 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)