Faster single-source shortest paths with negative real weights via proper hop distance
The textbook algorithm for single-source shortest paths with real-valued edge weights runs in $O(m n)$ time on a graph with $m$ edges and $n$ vertices. A recent breakthrough algorithm by Fineman [Fin24] takes $\tilde O(m n^{8/9})$ randomized time. We present an $\tilde O(m n^{4/5})$ randomized time...
Збережено в:
| Автори: | , , |
|---|---|
| Формат: | Стаття |
| Опубліковано: |
2024
|
| Предмети: | |
| Онлайн доступ: | https://arxiv.org/abs/2407.04872 http://arxiv.org/abs/2407.04872 |
| Теги: |
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|