Reduction from CNF-SAT to Approximate Betweenness Centrality: 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 10:5510:55, 15 February 2023‎ Admin talk contribs‎ 720 bytes +720‎ Created page with "FROM: CNF-SAT TO: Approximate Betweenness Centrality == Description == $\alpha$-approximation for any finite $\alpha$ (possibly depending on $m$) == Implications == if: to-time: $O(m^{2-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O*({2}^{({1}-\delta)n})$ for some $\delta > {0}$ == Year == 2015 == Reference == Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP..."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_CNF-SAT_to_Approximate_Betweenness_Centrality"