Shortest Paths in Matrix Multiplication Time
Lists
Only you see this
Abstract
In this paper we present an \({\tilde O}(W n^{\omega})\) time algorithm solving single source shortest path problem in graphs with integer weights from the set {–W,...,0,...,W}, where ω < 2.376 is the matrix multiplication exponent. For dense graphs with small edge weights, this result improves upon the algorithm of Goldberg that works in \({\tilde O}(mn^{0.5}{\rm log}W)\) time, and the Bellman-Ford algorithm that works in O(nm) time.
BibTeX
@inproceedings{sankowski2005shortest,
author = {Piotr Sankowski},
title = {{Shortest Paths in Matrix Multiplication Time}},
booktitle = {ESA},
year = {2005},
url = {https://openreview.net/forum?id=uy7qOhy5pt},
}Loading related content...