Shortcutting for Negative-Weight Shortest Paths
George Z. Li, Jason Li, Satish Rao, Junkai Zhang
2026年份
3被引次数
摘要
Consider the single-source shortest paths problem on a directed graph with real-valued edge weights. We solve this problem in O(n 2.5 log 4.5 n) time, improving on prior work of Fineman (STOC 2024) and Huang-Jin-Quanrud (SODA 2025, 2026) on dense graphs. Our main technique is an shortcutting procedure that iteratively reduces the number of negative-weight edges along shortest paths by a constant factor.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
它引用的顶会 Paper6
- Negative-Weight Single-Source Shortest Paths in Near-linear TimeAaron Bernstein, Danupon Nanongkai, Christian Wulff-NilsenFOCS 2022 · 被引用 24 次
- Breaking the Sorting Barrier for Directed Single-Source Shortest PathsRan Duan, Jiayi Mao, Xiao Mao, Xinkai Shu 等STOC 2025 · 被引用 8 次
- A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted GraphsRan Duan, Jiayi Mao, Xinkai Shu, Longhui YinFOCS 2023 · 被引用 6 次
- Faster single-source shortest paths with negative real weights via proper hop distanceYufan Huang, Peter Jin, Kent QuanrudSODA 2025 · 被引用 5 次
- Single-Source Shortest Paths with Negative Real Weights in Õ(mn8/9) TimeJeremy T. FinemanSTOC 2024 · 被引用 3 次
相关 Paper
- From Hop Reduction to Sparsification for Negative Length Shortest PathsKent Quanrud, Navid TajkhorshidSTOC 2026 · 被引用 1 次
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!Karl Bringmann, Alejandro Cassis, Nick FischerFOCS 2023 · 被引用 7 次
- Faster negative length shortest paths by bootstrapping hop reducersYufan Huang, Peter Jin, Kent QuanrudSODA 2026 · 被引用 2 次
- Incremental Single Source Shortest Paths in Sparse DigraphsShiri Chechik, Tianyi ZhangSODA 2021 · 被引用 5 次
- Deterministic Padded Decompositions and Negative-Weight Shortest PathsJason LiSTOC 2026 · 被引用 6 次
