Single-source shortest-paths on arbitrary directed graphs in linear average-case time

MaRDI QIDQ2768384zbMATH OpenFDO

Authors Ulrich Meyer

Publication date 22 July 2002

zbMATH Keywords

RAM algorithmshortest-paths algorithmssparse graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Simpler computation of single-source shortest paths in linear average time
• STACS 2004
• New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(12)

• A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing
• Simpler computation of single-source shortest paths in linear average time
• New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches
• Undirected single-source shortest paths with positive integer weights in linear time
• Engineering Route Planning Algorithms
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• A forward-backward single-source shortest paths algorithm
• STACS 2004
• Two-level heaps: a new priority queue structure with applications to the single source shortest path problem
• A faster algorithm for the single source shortest path problem with few distinct positive lengths

This page was built for publication: Single-source shortest-paths on arbitrary directed graphs in linear average-case time

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