Reduction from Directed, Weighted APSP to Dynamic Bipartite Maximum-Weight Matching

From Algorithm Wiki
Jump to navigation Jump to search

FROM: Directed, Weighted APSP TO: Dynamic Bipartite Maximum-Weight Matching

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/abstract/document/6979028?casa_token=daaoBjrHUa4AAAAA:DCjk_WMWZ5Is6KvGpmS8a2bL9LskvV0P1zEG4U2u-Tm_C8sixu1w65OpTyjml1HEpaikXhtYsg

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Reduction_from_Directed,_Weighted_APSP_to_Dynamic_Bipartite_Maximum-Weight_Matching&oldid=45176"