Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915579249557504 |
|---|---|
| author | Li, Jason Mowry, Connor Rao, Satish |
| author_facet | Li, Jason Mowry, Connor Rao, Satish |
| contents | We present a faster algorithm for low-diameter decompositions on directed graphs, matching the $O(\log n\log\log n)$ loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to $O((m+n\log\log n)\log n\log\log n)$ in expectation. We then apply our faster low-diameter decomposition to obtain an algorithm for negative-weight single source shortest paths on integer-weighted graphs in $O((m+n\log\log n)\log(nW)\log n\log\log n)$ time, a nearly log-factor improvement over the algorithm of Bringmann, Cassis, and Fischer (FOCS 2023). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions Li, Jason Mowry, Connor Rao, Satish Data Structures and Algorithms We present a faster algorithm for low-diameter decompositions on directed graphs, matching the $O(\log n\log\log n)$ loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to $O((m+n\log\log n)\log n\log\log n)$ in expectation. We then apply our faster low-diameter decomposition to obtain an algorithm for negative-weight single source shortest paths on integer-weighted graphs in $O((m+n\log\log n)\log(nW)\log n\log\log n)$ time, a nearly log-factor improvement over the algorithm of Bringmann, Cassis, and Fischer (FOCS 2023). |
| title | Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.22721 |