Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.19207 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909658705297408 |
|---|---|
| author | Liu, Yang P. |
| author_facet | Liu, Yang P. |
| contents | We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $[1, W]$, and maintains $(1+ε)$-approximate shortest path distances from a fixed source $s$ to all other vertices. The algorithm is deterministic and runs in total time $m^{1+o(1)}\log W$, for any $ε> \exp(-(\log m)^{0.99})$. This is achieved by designing a nonstandard interior point method to crudely detect when the distances from $s$ other vertices $v$ have decreased by a $(1+ε)$ factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19207 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method Liu, Yang P. Data Structures and Algorithms We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $[1, W]$, and maintains $(1+ε)$-approximate shortest path distances from a fixed source $s$ to all other vertices. The algorithm is deterministic and runs in total time $m^{1+o(1)}\log W$, for any $ε> \exp(-(\log m)^{0.99})$. This is achieved by designing a nonstandard interior point method to crudely detect when the distances from $s$ other vertices $v$ have decreased by a $(1+ε)$ factor, and implementing it using the deterministic min-ratio cycle data structure of [Chen-Kyng-Liu-Meierhans-Probst, STOC 2024]. |
| title | Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.19207 |