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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

(6)

• A bidirectional shortest-path algorithm with good average-case behavior
• Simpler computation of single-source shortest paths in linear average time
• 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
• Lower bounds for non-adaptive shortest path relaxation
• Lower bounds for adaptive relaxation-based algorithms for single-source shortest paths

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)