{"ID":2843155,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.07859","arxiv_id":"2511.07859","title":"Deterministic Padded Decompositions and Negative-Weight Shortest Paths","abstract":"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.","short_abstract":"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.","url_abs":"https://arxiv.org/abs/2511.07859","url_pdf":"https://arxiv.org/pdf/2511.07859v2","authors":"[\"Jason Li\"]","published":"2025-11-11T05:51:10Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}