Reduction from Directed, Weighted APSP to Dynamic $st$-Shortest Path
Jump to navigation
Jump to search
FROM: Directed, Weighted APSP TO: Dynamic $st$-Shortest Path
Description
Implications
if: to-time: amortized $O(n^{2-\epsilon})$ update and query times in decremental or incremental graphs
then: APSP Hypothesis is false
Year
2014
Reference
Abboud, Amir, and Virginia Vassilevska Williams. "Popular conjectures imply strong lower bounds for dynamic problems." In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434-443. IEEE, 2014.