View source for Reduction from BMM to 1-sensitive (4/3)-approximate decremental diameter

FROM: [[BMM]] TO: [[1-sensitive (4/3)-approximate decremental diameter]]

== Description == 



== Implications == 

assume: BMM<br/>then: combinatorial algorithms cannot solve target with preprocessing time $O(n^{3-\epsilon})$, and update and query times $O(n^{2-\epsilon})$ for any $\epsilon > {0}$ in undirected unweighted graphs

== Year == 

2017

== Reference == 

Henzinger, M., Lincoln, A., Neumann, S., & Williams, V. V. (2017). Conditional hardness for sensitivity problems. arXiv preprint arXiv:1703.01638.

https://arxiv.org/pdf/1703.01638.pdf