Shortest paths in random weighted graphs

DOI10.1007/bfb0030835zbMath1527.05159OpenAlexW1560319079MaRDI QIDQ6085709

Scott K. Walley, Harry H. Tan

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0030835

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Cites Work

• Unnamed Item
• The shortest-path problem for graphs with random arc-lengths
• Faster algorithms for the shortest path problem
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• On Shortest Paths in Graphs with Random Weights
• Fibonacci heaps and their uses in improved network optimization algorithms
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$

This page was built for publication: Shortest paths in random weighted graphs