Reduction from Triangle Collection* to dynamic 4/3-Diameter: Difference between revisions
Jump to navigation
Jump to search
(Created page with "FROM: Triangle Collection* TO: dynamic 4/3-Diameter == Description == == Implications == assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no incremental (or decremental) algorithm that approximates the diameter of unweighted graph within a factor of ${4}/{3}-\epsilon$ running in amortized time $O(n^{1/{2}-\epsilon'})$ for any $\epsilon,\epsilon' > {0}$. Furthermore, if we allow node insertions in the incremental case the bound is...") |
No edit summary |
||
| Line 7: | Line 7: | ||
== Implications == | == Implications == | ||
assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no | assume: SETH or {3}SUM Hypothesis or APSP Hypothesis<br/>then: there exists no static ${4}/{3}-\epsilon$ approximation to the diameter on unweighted graphs running in $O((n\sqrt{m})^{1-\epsilon'})$ time for any $\epsilon,\epsilon' > {0}$ and an number of edges $m$ | ||
== Year == | == Year == | ||
Revision as of 12:19, 15 February 2023
FROM: Triangle Collection* TO: dynamic 4/3-Diameter
Description
Implications
assume: SETH or {3}SUM Hypothesis or APSP Hypothesis
then: there exists no static ${4}/{3}-\epsilon$ approximation to the diameter on unweighted graphs running in $O((n\sqrt{m})^{1-\epsilon'})$ time for any $\epsilon,\epsilon' > {0}$ and an number of edges $m$
Year
2016
Reference
Dahlgaard, S. (2016). On the hardness of partially dynamic graph problems and connections to diameter. arXiv preprint arXiv:1602.06705.