scientific article; zbMATH DE number 1416161

DOI<33::AID-RSA3>3.0.CO;2-0 10.1002/(SICI)1098-2418(200001)16:1<33::AID-RSA3>3.0.CO;2-0zbMath0951.68109MaRDI QIDQ4943352

Kurt Mehlhorn, Colin Cooper, Volker Priebe, Alan M. Frieze

Publication date: 12 December 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

shortest path problemsvertex-potential model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (2)

Joint chance constrained shortest path problem with Copula theory ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• The shortest-path problem for graphs with random arc-lengths
• The expected length of a shortest path
• All-pairs shortest paths and the essential subgraph
• On a routing problem
• Faster algorithms for the shortest path problem
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• A theorem on the expected complexity of dijkstra's shortest path algorithm
• On Shortest Paths in Graphs with Random Weights
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Scaling Algorithms for the Shortest Paths Problem
• 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: