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

\(\Delta\)-stepping algorithmapproximate Bucket implementationBellman-Ford algorithmgraphs with random edge weightsPallottino's incremental graph algorithmthreshold approachtopological ordering SSSP algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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)

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

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)