Reduction from 3-OV to Diameter 3 vs 7: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 12:1812:18, 15 February 2023‎ Admin talk contribs‎ 469 bytes +469‎ Created page with "FROM: 3-OV TO: Diameter 3 vs 7 == Description == == Implications == If: to-time: $O(N^{({3}/{2}-\epsilon)}$ where $N=n^{2} d^{2}$ and $\epsilon > {0}$<br/>Then: from-time: $n^{3-{2}\epsilon} poly(d)$ == Year == 2018 == Reference == Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. https://dl.acm.org/doi/pdf/10.1145/3188745.3188950"
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_3-OV_to_Diameter_3_vs_7"