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

DOI10.1007/978-3-642-19754-3_22MaRDI QIDQ2999348zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(5)

• Lower bounds for non-adaptive shortest path relaxation
• A bidirectional shortest-path algorithm with good average-case behavior
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Simpler computation of single-source shortest paths in linear average 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)