New pages

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

• 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")
• 10:54, 15 February 2023 ‎Cheriton-Tarjan (dense) (Undirected, Dense MST Minimum Spanning Tree (MST)) (hist | edit) ‎[318 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ 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")
• 10:54, 15 February 2023 ‎Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[409 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://dl.acm.org/citation.cfm?id=28874")
• 10:54, 15 February 2023 ‎Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) ‎[270 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(V)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==")
• 10:54, 15 February 2023 ‎Multistep (SCCs Strongly Connected Components) (hist | edit) ‎[308 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}+E)$ == Space Complexity == $O(V+E)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6877288")
• 10:54, 15 February 2023 ‎Geldenhuys-Valmari (SCCs Strongly Connected Components) (hist | edit) ‎[410 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$? words ((follow-up from Tarjan's algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6")
• 10:54, 15 February 2023 ‎(many more...) (2-dimensional Convex Hull, Dynamic Convex Hull) (hist | edit) ‎[221 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == == Reference ==")
• 10:54, 15 February 2023 ‎Dynamic 2-d Convex Hull, Overmars and van Leeuwen (2-dimensional Convex Hull, Dynamic Convex Hull) (hist | edit) ‎[359 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n)$) per operation, $O(n*log^{2}(n)$) total == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/002200008190012X?via%3Dihub")
• 10:54, 15 February 2023 ‎Online 2-d Convex Hull, Preparata (2-dimensional Convex Hull, Online Convex Hull) (hist | edit) ‎[340 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ per operation, $O(n*log(n)$) total == Space Complexity == $O(n)$ words (easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://dl.acm.org/doi/abs/10.1145/359131.359132")
• 10:54, 15 February 2023 ‎N-dimensional Quickhull (d-dimensional Convex Hull Convex Hull) (hist | edit) ‎[353 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f(h)$/h) where f(h) denotes the maximum number of facets with h vertices == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/pdf/10.1145/235815.235821")
• 10:54, 15 February 2023 ‎Chand-Kapur, Gift Wrapping (d-dimensional Convex Hull Convex Hull) (hist | edit) ‎[286 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*f_1)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1970 == Reference == https://dl.acm.org/doi/pdf/10.1145/321556.321564")
• 10:54, 15 February 2023 ‎Seidel's Shelling Algorithm (d-dimensional Convex Hull Convex Hull) (hist | edit) ‎[295 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}+f_1*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://dl.acm.org/doi/pdf/10.1145/12130.12172")
• 10:54, 15 February 2023 ‎NIEVERGELT. J.. AND PREPARATA (Section 2) (Reporting all intersection points / general polygons Line segment intersection) (hist | edit) ‎[388 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O((n+k)$log n) == Space Complexity == $O(n+k)$ words (https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1982 == Reference == https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf")
• 10:54, 15 February 2023 ‎Jiang, Song, Weinstein and Zhang ( Linear Programming) (hist | edit) ‎[462 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^(max(omega, {2.5}-alpha/{2}, {37}/{18}))*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication; currently $O(n^{2.37285956})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/1810.07896")
• 10:54, 15 February 2023 ‎CHAZELLE 1986 (Counting number of intersection points / line segments Line segment intersection) (hist | edit) ‎[380 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.695})$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000086900255) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0022000086900255")
• 10:54, 15 February 2023 ‎Parameter-expanded expectation maximization (PX-EM) (Maximum Likelihood Methods in Unknown Latent Variables Maximum Likelihood Methods in Unknown Latent Variables) (hist | edit) ‎[452 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n+r)$? words (Stores current theta (+ alpha) and Z guesses, which is updated each iteration. Also assumes description of log-likelihood takes O(n+r) auxiliary space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1998 == Reference == http://www.stat.ucla.edu/~ywu/research/papers/PXEM.pdf")
• 10:54, 15 February 2023 ‎Vaidya ( Linear Programming) (hist | edit) ‎[346 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(((m+n)$n^{2}+(m+n)^{1.5}*n)L^{2} logL loglogL) == Space Complexity == $O((nm+n^{2})$L)? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01580859")
• 10:54, 15 February 2023 ‎Peng, Vempala (Sparse Linear system of equations) (hist | edit) ‎[473 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(max(m^{(omega-{2})/(omega-{1})}*n^{2}, n^{({5}*omega-{4})/(omega+{1})})*log^{2}(k/epsilon))$ where omega is the exponent on the complexity of matrix multiplication; currently $O(n^{2.331642})$ == Space Complexity == words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/abs/2007.10254")
• 10:54, 15 February 2023 ‎Asymptotically fast Toeplitz algorithms (Toeplitz Linear system of equations) (hist | edit) ‎[319 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log^{2}(n)$) == Space Complexity == $O(n*log^{2}(n)$)? words (upper bound) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008? == Reference == https://epubs.siam.org/doi/10.1137/040617200")
• 10:54, 15 February 2023 ‎Matrix inverse (General Linear system of equations) (hist | edit) ‎[384 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega)$ where omega is the exponent on the complexity of matrix multiplication;<br/>currently $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (equivalent to matrix multiplication) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
• 10:54, 15 February 2023 ‎Koivisto ( Chromatic Polynomial) (hist | edit) ‎[306 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
• 10:54, 15 February 2023 ‎LU decomposition (General Linear system of equations) (hist | edit) ‎[261 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == O (n^{3}) == Space Complexity == $O(n^{2})$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == == Reference ==")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Proposition 3 ( Chromatic Polynomial) (hist | edit) ‎[402 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) => $O({1.292}^n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Zykov (deletion-contraction) ( Chromatic Polynomial) (hist | edit) ‎[253 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O((({1}+sqrt5)$/{2})^(n+m)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1949 == Reference ==")
• 10:54, 15 February 2023 ‎Fomin; Gaspers & Saurabh ( (hist | edit) ‎[304 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.6262}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-73545-8_9")
• 10:54, 15 February 2023 ‎Fürer, Kasiviswanathan ( (hist | edit) ‎[335 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7702}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.634.4498&rep=rep1&type=pdf")
• 10:54, 15 February 2023 ‎Angelsmark, Jonsson ( (hist | edit) ‎[304 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7879}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-45193-8_6")
• 10:54, 15 February 2023 ‎Koivisto ( Chromatic Number) (hist | edit) ‎[306 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031393")
• 10:54, 15 February 2023 ‎BFS/DFS for connected components ( (hist | edit) ‎[267 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ == Space Complexity == $O(n)$ auxiliary words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference ==")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Proposition 2 ( Chromatic Number) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Theorem 1 ( Chromatic Number) (hist | edit) ‎[384 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Byskov ( Chromatic Number) (hist | edit) ‎[407 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({80}^(n/{5})$) ~ $O({2.4023}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/pii/S0167637704000409")
• 10:54, 15 February 2023 ‎Lawler ( Chromatic Number) (hist | edit) ‎[417 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn({1}+{3}^({1}/{3})$)^n) == Space Complexity == $O({2}^n*log(n)$) words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
• 10:54, 15 February 2023 ‎Eppstein ( Chromatic Number) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(({4}/{3}+{3}^({4}/{3})$/{4})^n) ~ $O({2.4151}^n)$ == Space Complexity == $O({2}^n)$ words (https://arxiv.org/pdf/cs/0011009.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://arxiv.org/pdf/cs/0011009.pdf")
• 10:54, 15 February 2023 ‎Christofides ( Chromatic Number) (hist | edit) ‎[379 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n!*poly(n)$) == Space Complexity == $O(poly(n)$) words (https://link.springer.com/article/10.1007/s00453-007-9149-8) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://academic.oup.com/comjnl/article/14/1/38/356253?login=true")
• 10:54, 15 February 2023 ‎Zamir ( 6 - Graph Coloring) (hist | edit) ‎[341 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Proposition 2 ( 6 - Graph Coloring) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Theorem 1 ( 6 - Graph Coloring) (hist | edit) ‎[384 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Byskov, Theorem 20 ( 6 - Graph Coloring) (hist | edit) ‎[402 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2680}^n)$ == Space Complexity == $O({2}^n)$ words (https://www.sciencedirect.com/science/article/pii/S0167637704000409) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
• 10:54, 15 February 2023 ‎Byskov, Theorem 14 ( 6 - Graph Coloring) (hist | edit) ‎[325 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.3289}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
• 10:54, 15 February 2023 ‎Zamir ( 5 - Graph Coloring) (hist | edit) ‎[342 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(({2}-eps)$^n) for some eps>{0} == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://drops.dagstuhl.de/opus/volltexte/2021/14182/pdf/LIPIcs-ICALP-2021-113.pdf")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Proposition 2 ( 5 - Graph Coloring) (hist | edit) ‎[375 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.2461}^n)$ == Space Complexity == $O(poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Bjorklund, Husfeldt, Theorem 1 ( 5 - Graph Coloring) (hist | edit) ‎[384 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n)$) == Space Complexity == $O({2}^n*poly(n)$) words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4031392")
• 10:54, 15 February 2023 ‎Byskov ( 5 - Graph Coloring) (hist | edit) ‎[325 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({2.1592}^n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
• 10:54, 15 February 2023 ‎Alman, Vassilevska Williams ( Matrix Multiplication) (hist | edit) ‎[363 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.37285956})$ == Space Complexity == $O(n^{2})$ words (through re-use of space in recursive branches (response from Virginia)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://arxiv.org/pdf/2010.05846.pdf")
• 10:54, 15 February 2023 ‎Method of Four Russians ( Matrix Multiplication) (hist | edit) ‎[381 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}/log n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=On+economical+construction+of+the+transitive+closure+of+an+oriented+graph.&btnG=")
• 10:54, 15 February 2023 ‎Goldberg & Rao (Parallel) (Integer Maximum Flow Maximum Flow) (hist | edit) ‎[344 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.66} log(V)$ log(U)) == Space Complexity == $O(V^{2})$ words (https://dl.acm.org/citation.cfm?id=290181) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181")

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