New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
© 2020 ACM. In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph G=(V,E) subject to edge insertions and deletions and a source vertex sg V, and the goal is to maintain the distance d(s,t) for all tg V. Fine-grained complexity has provided strong lower bounds for exact par...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137818 |