Reduction from Directed, Weighted APSP to Dynamic $st$-Shortest Path

From Algorithm Wiki
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.

https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Reduction_from_Directed,_Weighted_APSP_to_Dynamic_$st$-Shortest_Path&oldid=45174"