New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches

DOI10.1007/978-3-642-19754-3_22zbMATH Open1325.68111OpenAlexW2153730131MaRDI QIDQ2999348FDOQ2999348

Authors: Ulrich Meyer, Andrei Negoescu, Volker Weichert 

Publication date: 12 May 2011

Published in: Theory and Practice of Algorithms in (Computer) Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19754-3_22

Recommendations

• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Simpler computation of single-source shortest paths in linear average time
• A forward-backward single-source shortest paths algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (5)

• A bidirectional shortest-path algorithm with good average-case behavior
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Lower bounds for non-adaptive shortest path relaxation
• 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: New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2999348)