确定性填充分解和负-负-负-负-负-正数最短路径
Deterministic Padded Decompositions and Negative-Weight Shortest Paths
Jason Li
arXiv
2025年11月11日
我们获得了第一个近线性时间确定性算法,用于负重单源最短路径在整数加权图形上。 我们的主要成分是在定向图形上填充分解的确定性结构,这可能是独立的兴趣。
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.