Reduction from CNF-SAT to Approximate Diameter
Revision as of 11:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Approximate Diameter == Description == == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation<br/>then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$ == Year == 2013 == Reference == L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013. https://people.csail.mit....")
FROM: CNF-SAT TO: Approximate Diameter
Description
Implications
if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$ for a $({3}/{2} - \epsilon)$-approximation
then: from-time: $O*(({2}-\delta)^n)$ for constant $\delta > {0}$
Year
2013
Reference
L. Roditty and V. Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524, 2013.
https://people-csail-mit-edu.ezproxy.canberra.edu.au/virgi/diam.pdf