Negative-Weight Single-Source Shortest Paths in Near-linear Time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Negative-Weight Single-Source Shortest Paths in Near-linear Time. / Bernstein, Aaron; Nanongkai, Danupon; Wulff-Nilsen, Christian.
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2022. p. 600-611 (Annual IEEE Symposium on Foundations of Computer Science).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Negative-Weight Single-Source Shortest Paths in Near-linear Time
AU - Bernstein, Aaron
AU - Nanongkai, Danupon
AU - Wulff-Nilsen, Christian
PY - 2022
Y1 - 2022
N2 - We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog(8)(n) logW) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are (O) over tilde ((m + n(1.5)) logW) [BLNPSSSW FOCS'20] and m(4/3+o(1)) logW [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic (O) over tilde (m root n logW) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
AB - We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog(8)(n) logW) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are (O) over tilde ((m + n(1.5)) logW) [BLNPSSSW FOCS'20] and m(4/3+o(1)) logW [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic (O) over tilde (m root n logW) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
KW - graphs and networks
KW - path and circuit problems
KW - graph algorithms
KW - analysis of algorithms
KW - SCALING ALGORITHMS
KW - GRAPHS
U2 - 10.1109/FOCS54457.2022.00063
DO - 10.1109/FOCS54457.2022.00063
M3 - Article in proceedings
T3 - Annual IEEE Symposium on Foundations of Computer Science
SP - 600
EP - 611
BT - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
PB - IEEE
T2 - 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)
Y2 - 31 October 2022 through 3 November 2022
ER -
ID: 337602711