Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
2026年份
6被引次数
1顶会引用
摘要
We obtain the first near-linear time deterministic algorithm for negative-weight single-source shortest paths on integer-weighted graphs. Our main ingredient is a deterministic construction of a padded decomposition on directed graphs, which may be of independent interest.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
引用它的顶会 Paper1
问问它们各自怎么用它它引用的顶会 Paper8
- A Deterministic Almost-Linear Time Algorithm for Minimum-Cost FlowJan van den Brand, Li Chen, Richard Peng, Rasmus Kyng 等FOCS 2023 · 被引用 28 次
- Negative-Weight Single-Source Shortest Paths in Near-linear TimeAaron Bernstein, Danupon Nanongkai, Christian Wulff-NilsenFOCS 2022 · 被引用 24 次
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!Karl Bringmann, Alejandro Cassis, Nick FischerFOCS 2023 · 被引用 7 次
- Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path CoversBernhard Haeupler, Yonggang Jiang, Thatchaphol SaranurakSTOC 2026 · 被引用 5 次
- Faster single-source shortest paths with negative real weights via proper hop distanceYufan Huang, Peter Jin, Kent QuanrudSODA 2025 · 被引用 5 次
相关 Paper
- Faster Negative-Weight Shortest Paths and Directed Low-Diameter DecompositionsJason Li, Connor Mowry, Satish RaoSODA 2026
- Breaking the Sorting Barrier for Directed Single-Source Shortest PathsRan Duan, Jiayi Mao, Xiao Mao, Xinkai Shu 等STOC 2025 · 被引用 8 次
- Undirected (1+ε)-shortest paths via minor-aggregates: near-optimal deterministic parallel and distributed algorithmsVáclav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic 等STOC 2022 · 被引用 22 次
- Exact Shortest Paths with Rational Weights on the Word RAMAdam Karczmarz, Wojciech Nadara, Marek SokolowskiSODA 2024 · 被引用 1 次
- Parallel Exact Shortest Paths in Almost Linear Work and Square Root DepthNairen Cao, Jeremy T. FinemanSODA 2023 · 被引用 4 次
