Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
From MaRDI portal
Publication:5862374
DOI10.26493/1855-3974.2467.497zbMath1484.05198OpenAlexW3155021337MaRDI QIDQ5862374
Andrej Brodnik, Rok Požar, Marko Grgurovič
Publication date: 9 March 2022
Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.26493/1855-3974.2467.497
Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Combinatorial probability (60C05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- A guided tour of Chernoff bounds
- A new approach to all-pairs shortest paths on real-weighted graphs
- Shortest paths algorithms: Theory and experimental evaluation
- Solving all-pairs shortest path by single-source computations: theory and practice
- An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
- Experimental analysis of dynamic all pairs shortest path algorithms
- The Longest Minimum-Weight Path in a Complete Graph
- A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
- An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
- One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
- All-Pairs Shortest Paths in $O(n^2)$ time with high probability
- A new approach to dynamic all pairs shortest paths
- A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
- A Theorem on Boolean Matrices
This page was built for publication: Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
