Finding real-valued single-source shortest paths in o(n 3) expected time

DOI10.1007/3-540-61310-2_8zbMath1415.90137OpenAlexW1426993502MaRDI QIDQ4645916

Stavros G. Kolliopoulos, Clifford Stein

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_8

zbMATH Keywords

expected timeshort pathshort path treeshort path problemedge cost

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The shortest-path problem for graphs with random arc-lengths
• On the exponent of all pairs shortest path problem
• On the Shortest Route Through a Network
• On a routing problem
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• On Shortest Paths in Graphs with Random Weights
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• A Note on Spira’s Algorithm for the All-Pairs Shortest-Path Problem
• A randomized linear-time algorithm to find minimum spanning trees
• Faster Scaling Algorithms for Network Problems
• Scaling Algorithms for the Shortest Paths Problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• An Õ(n²) algorithm for minimum cuts
• 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: Finding real-valued single-source shortest paths in o(n 3) expected time