[2203.03456] Negative-Weight Single-Source Shortest Paths in Near-linear Time
source link: https://arxiv.org/abs/2203.03456
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 7 Mar 2022 (v1), last revised 30 Oct 2022 (this version, v4)]
Negative-Weight Single-Source Shortest Paths in Near-linear Time
We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(m\log^8(n)\log W) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are \tilde O((m+n^{1.5})\log W) [BLNPSSSW FOCS'20] and m^{4/3+o(1)}\log W [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 \tilde O(m\sqrt{n}\log W) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
| Comments: | Simplified algorithm for Low-Diameter Decomposition and minor corrections |
| Subjects: | Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2203.03456 [cs.DS] |
| (or arXiv:2203.03456v4 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2203.03456 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK