New pages

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)

• 10:55, 15 February 2023 ‎Reduction from Nondecreasing Triangle to Triangle in Unweighted Graph (hist | edit) ‎[403 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Nondecreasing Triangle TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1")
• 10:55, 15 February 2023 ‎Reduction from $(\min, \leq)$ Product to Triangle in Unweighted Graph (hist | edit) ‎[410 bytes] ‎Admin (talk | contribs) (Created page with "FROM: $(\min, \leq)$ Product TO: Triangle in Unweighted Graph == Description == == Implications == if: to-time: $T(n)$ for unweighted graph<br/>then: from-time: $O(n^{3/2} \sqrt{T(O(n))} \log n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 7.1")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle to Price Query (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle TO: Price Query == Description == == Implications == if: to-time: $O(n^{2} / f(n))$ to answer any subsequent price query after $n$-node edge-weighted graph is preprocessed in $O(^k)$ time for some constant $k > {0}$<br/>then: from-time: $O(n^{3} / f(n^{1/({2}k)})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/...")
• 10:55, 15 February 2023 ‎Reduction from BMM to Independent Set Queries (hist | edit) ‎[513 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.or...")
• 10:55, 15 February 2023 ‎Reduction from Triangle Detection to Independent Set Queries (hist | edit) ‎[528 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Independent Set Queries == Description == == Implications == if: to-time: $O(n^{2} / \log^c n)$ to answer all subsequent batches of $\log n$ independent set queries from a graph that takes $O(n^k)$ time to preprocess for some $c,k > {0}$<br/>then: from-time: $O(n^{3} / \log^{c+1} n)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. ht...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Replacement Paths Problem (RPP) (hist | edit) ‎[494 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Replacement Paths Problem (RPP) == Description == == Implications == if: to-time: $T(n) polylog M$ in graphs with integer weights in $({0}, M)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3})) polylog M)$ in graphs with integer weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/318...")
• 10:55, 15 February 2023 ‎Reduction from Distance Product to Second Shortest Simple Path (hist | edit) ‎[503 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Distance Product TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(nW)) \log W)$ for two $n\times n$ matrices with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Second Shortest Simple Path (hist | edit) ‎[497 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $O(n^{2} T(O(n^{1/3}), O(n^{2}W)) \log Wn)$ for graphs with weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.114...")
• 10:55, 15 February 2023 ‎Reduction from Minimum Triangle to Second Shortest Simple Path (hist | edit) ‎[479 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Minimum Triangle TO: Second Shortest Simple Path == Description == == Implications == if: to-time: $T(n,W)$ where there are $n$ nodes and integer weights in $({0}, W)$<br/>then: from-time: $T(O(n), O(nW))$ for $n$ node graph with integer weights in $(-W, W)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem...")
• 10:55, 15 February 2023 ‎Reduction from Maximum Subarray to Negative Triangle Detection (hist | edit) ‎[411 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Maximum Subarray TO: Negative Triangle Detection == Description == == Implications == == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/abs/10.5555/314613.314823")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Maximum Subarray (hist | edit) ‎[307 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Maximum Subarray == Description == == Implications == == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.4")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Shortest Cycle (hist | edit) ‎[463 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Shortest Cycle == Description == == Implications == if: to-time: $T(n,M)$ where there are $n$ nodes and weights in $({1}, M)$<br/>then: from-time: $T(n, O(M))$ where there are $n$ nodes and weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.3")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Metricity (hist | edit) ‎[494 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Metricity == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$, and $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3...")
• 10:55, 15 February 2023 ‎Reduction from Metricity to Negative Triangle Detection (hist | edit) ‎[495 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Metricity TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{2}) + T(O(n), O(M))$ where $T(n,M)$ is nondecreasing<br/>then: from-time: $O(n^{2}) + T(O(n), O(M))$ where the metricity problem is on $(n)$ s.t. all distances are in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Undirected, Weighted APSP (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Undirected, Weighted APSP == Description == == Implications == if: to-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$<br/>then: from-time: $T(n, M)$ where graph has weights in $({0}, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1")
• 10:55, 15 February 2023 ‎Reduction from Undirected, Weighted APSP to Directed, Weighted APSP (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Undirected, Weighted APSP TO: Directed, Weighted APSP == Description == == Implications == if: to-time: $T(n, M)$ where graph has weights in $({0}, M)$<br/>then: from-time: $T(n, \Theta(M))$ where digraph has weights in $(-M, M)$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 5.1")
• 10:55, 15 February 2023 ‎Reduction from All Pairs Minimum Witness (APMW) to Negative Triangle Detection (hist | edit) ‎[382 bytes] ‎Admin (talk | contribs) (Created page with "FROM: All Pairs Minimum Witness (APMW) TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T(n^{1/3})n^{2})$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.5")
• 10:55, 15 February 2023 ‎Reduction from Minimum Witness Finding to Negative Triangle Detection (hist | edit) ‎[408 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Minimum Witness Finding TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$ where $n$ is the number of nodes in the graph<br/>then: from-time: $O(T(n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.4")
• 10:55, 15 February 2023 ‎Reduction from Maximum Subarray to Distance Product (hist | edit) ‎[499 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Maximum Subarray TO: Distance Product == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$<br/>then: from-time: $O(n^{3-\epsilon})$ == Year == 1998 == Reference == Hisao Tamaki and Takeshi Tokuyama. 1998. Algorithms for the maximum subarray problem based on matrix multiplication. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). 446–452. https://dl.acm.org/doi/a...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Listing to Negative Triangle Detection (hist | edit) ‎[578 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Listing TO: Negative Triangle Detection == Description == == Implications == if: to-time: $O(n^{3-\epsilon}\log^c M)$ for some $\epsilon > {0}$ and where $M$ is the maxint of $R$<br/>then: from-time: $O(n^{3-\epsilon'}\log^c M)$ for some $\epsilon' > {0}$ for listing $\Delta = O(n^{3-\delta})$ negative triangles with fixed $\delta > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Betw...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Search to Negative Triangle Detection (hist | edit) ‎[392 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Search TO: Negative Triangle Detection == Description == == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(T(n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Lemma 4.1")
• 10:55, 15 February 2023 ‎Reduction from Matrix Product to Negative Triangle Detection (hist | edit) ‎[524 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Matrix Product TO: Negative Triangle Detection == Description == Generic runtimes for two $n \times n$ matrices == Implications == if: to-time: $T(n)$ where $T(n)/n$ is decreasing<br/>then: from-time: $O(n^{2} \cdot T(n^{1/3})\log W)$ for two $n\times n$ matrices where $W$ is the maxint of $R$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.o...")
• 10:55, 15 February 2023 ‎Reduction from Negative Triangle Detection to Matrix Product Verification (hist | edit) ‎[371 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Negative Triangle Detection TO: Matrix Product Verification == Description == == Implications == if: to-time: $T(n)$<br/>then: from-time: $O(T({2}n))$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 4.1")
• 10:55, 15 February 2023 ‎Reduction from BMM to CFG Parsing (hist | edit) ‎[467 bytes] ‎Admin (talk | contribs) (Created page with "FROM: BMM TO: CFG Parsing == Description == == Implications == if: to-time: $O(gn^{3-\epsilon})$ for some $\epsilon > {0}$ where $g$ is the size of the CFG and $n$ is the size of the string<br/>then: from-time: $O(n^{3-\epsilon/3})$ where $n \times n$ matrix == Year == 2002 == Reference == L. Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1–15. https://arxiv.org/abs/cs/0112018")
• 10:55, 15 February 2023 ‎Reduction from CFG Parsing to BMM (hist | edit) ‎[467 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CFG Parsing TO: BMM == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix<br/>then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG == Year == 1975 == Reference == L. G. Valiant. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308–315. https://www.sciencedirect.com/science/article/pii/S0022000075800468")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Multiple Local Alignment (hist | edit) ‎[607 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Multiple Local Alignment == Description == == Implications == if: to-time: $N^{k-\epsilon}$ for some $\epsilon > {0}$ on $k$ binary strings of length $n$ with $k$-wise scoring<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Langu...")
• 10:55, 15 February 2023 ‎Reduction from Directed, Weighted APSP to Negative Triangle Detection (hist | edit) ‎[421 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Directed, Weighted APSP TO: Negative Triangle Detection == Description == == Implications == if: to-time: $n^{3-\epsilon}$ for some $\epsilon >{0}$<br/>then: from-time: $n^{3-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2018 == Reference == V. V. Williams, R. R. Williams, Subcubic Equivalences Between Path, Matrix, and Triangle Problems. 2018. https://dl.acm.org/doi/pdf/10.1145/3186893")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Longest Common Substring with don't cares (hist | edit) ‎[566 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Longest Common Substring with don't cares == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-51. Springe...")
• 10:55, 15 February 2023 ‎Reduction from CNF-SAT to Local Alignment (hist | edit) ‎[576 bytes] ‎Admin (talk | contribs) (Created page with "FROM: CNF-SAT TO: Local Alignment == Description == == Implications == if: to-time: $N^{2-\epsilon}$ for some $\epsilon > {0}$ on two binary strings of length $N$<br/>then: from-time: ${2}^{(n-\epsilon')}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium on Automata, Languages, and Programming, pp. 39-5...")
• 10:55, 15 February 2023 ‎Reduction from 3SUM to Local Alignment (hist | edit) ‎[625 bytes] ‎Admin (talk | contribs) (Created page with "FROM: 3SUM TO: Local Alignment == Description == == Implications == if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$<br/>then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2014 == Reference == Abboud, Amir, Virginia Vassilevska Williams, and Oren Weimann. "Consequences of faster alignment of sequences." In International Colloquium...")
• 10:55, 15 February 2023 ‎Reduction from 3SUM' to Static Dihedral Rotation Queries (hist | edit) ‎[491 bytes] ‎Admin (talk | contribs) (Created page with "FROM: 3SUM' TO: Static Dihedral Rotation Queries == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 2003 == Reference == Michael Soss, Jeff Erickson, Mark Overmars, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry, Volume 26, Issue 3, 2003, Pages 235-246 https://doi.org/10.1016/S0925...")
• 10:55, 15 February 2023 ‎Reduction from GeomBase to Planar Motion Planning (hist | edit) ‎[450 bytes] ‎Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Planar Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
• 10:55, 15 February 2023 ‎Reduction from Triangles Cover Triangle to 3D Motion Planning (hist | edit) ‎[462 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: 3D Motion Planning == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
• 10:55, 15 February 2023 ‎Reduction from Triangles Cover Triangle to Visible Triangle (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Triangles Cover Triangle TO: Visible Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
• 10:55, 15 February 2023 ‎Reduction from Visible Triangle to Triangles Cover Triangle (hist | edit) ‎[460 bytes] ‎Admin (talk | contribs) (Created page with "FROM: Visible Triangle TO: Triangles Cover Triangle == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
• 10:55, 15 February 2023 ‎Reduction from GeomBase to Visibility From Infinity (hist | edit) ‎[452 bytes] ‎Admin (talk | contribs) (Created page with "FROM: GeomBase TO: Visibility From Infinity == Description == == Implications == if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$<br/>then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$ == Year == 1995 == Reference == Anka Gajentaan, Mark H Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry, Volume 5, Issue 3, 1995, Pages 165-185 https://doi.org/10.1016/0925-7721(95)00022-2")
• 10:54, 15 February 2023 ‎Brandes (Weighted Betweenness Centrality (BC)) (hist | edit) ‎[390 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm + n^{2} \log n)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249")
• 10:54, 15 February 2023 ‎Brandes (Unweighted Betweenness Centrality (BC)) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O(n + m)$ (https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 2000 == Reference == https://www.tandfonline.com/doi/abs/10.1080/0022250x.2001.9990249")
• 10:54, 15 February 2023 ‎Thorup (positive integer weights; assumes constant-time multiplication Shortest Path (Undirected graphs)) (hist | edit) ‎[328 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (https://dl.acm.org/doi/10.1145/316542.316548) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://dl.acm.org/doi/10.1145/316542.316548")
• 10:54, 15 February 2023 ‎Dial's Algorithm (nonnegative integer weights Shortest Path (Directed graphs)) (hist | edit) ‎[337 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+LV)$ == Space Complexity == $O(V+L)$ words (keep track of vertices and L most recent buckets) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://dl.acm.org/doi/10.1145/363269.363610")
• 10:54, 15 February 2023 ‎Khuller, Matias (k-dimensional space, Euclidean metric Closest Pair Problem) (hist | edit) ‎[432 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == infinite (can be upper bounded by $O(n^{2})$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Real RAM == Year == 1995 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540185710498?via%3Dihub")
• 10:54, 15 February 2023 ‎Gabow et al, Section 3 (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[318 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+VlogV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168")
• 10:54, 15 February 2023 ‎Tarjan (directed, dense) (Directed (Optimum Branchings), Super Dense MST Minimum Spanning Tree (MST)) (hist | edit) ‎[360 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103")
• 10:54, 15 February 2023 ‎Gabow, Galil, Spencer (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[343 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(VlogV+Eloglog(logV/log(E/V + {2})$)) == Space Complexity == $O(E)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
• 10:54, 15 February 2023 ‎Chu-Liu-Edmonds Algorithm (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[326 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(EV)$ == Space Complexity == $O(E+V)$ words ((derived in sheet)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/71b/jresv71bn4p233_a1b.pdf")
• 10:54, 15 February 2023 ‎Tarjan (directed, general) (Directed (Optimum Branchings), General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[360 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(E)$ words (https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230070103")
• 10:54, 15 February 2023 ‎Pettie, Ramachandran (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[309 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == unknown but optimal == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/505241.505243")
• 10:54, 15 February 2023 ‎Fredman & Willard (Undirected, Integer Weights MST Minimum Spanning Tree (MST)) (hist | edit) ‎[323 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E+V)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Trans-dichotomous == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000005800649?via%3Dihub")
• 10:54, 15 February 2023 ‎Gabow et al, Section 2 (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[319 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*log(beta(E, V)$)) == Space Complexity == $O(E)$ auxiliary? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02579168")
• 10:54, 15 February 2023 ‎Cheriton-Tarjan (planar) (Undirected, Planar MST Minimum Spanning Tree (MST)) (hist | edit) ‎[317 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V)$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051")

(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)