New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 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")
- 10:54, 15 February 2023 Chen et al ( Maximum Flow) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)*log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2022 == Reference == https://arxiv.org/abs/2203.00671")
- 10:54, 15 February 2023 Gao, Liu, Peng ( Maximum Flow) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({3}/{2}-{1}/{328})$*log(U)*polylog(E)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.07233")
- 10:54, 15 February 2023 Brand et al ( Maximum Flow) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((E+V^{1.5})$log(U)polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2021 == Reference == https://arxiv.org/abs/2101.05719")
- 10:54, 15 February 2023 Kathuria, Liu, Sidford ( Maximum Flow) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({1}+o({1})$)/sqrt(eps)) == Space Complexity == $O(E)$ or $O(V^{2})$ ? words (unsure, please look) == Description == == Approximate? == Approximate Approximation Factor: 1+eps == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2020 == Reference == https://epubs.siam.org/doi/abs/10.1137/20M1383525")
- 10:54, 15 February 2023 Madry ( Maximum Flow) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^({10}/{7})$U^({1}/{7})polylog(V, E, log U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7782974")
- 10:54, 15 February 2023 Lee, Sidford ( Maximum Flow) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E*sqrt(V)$*log^{2}(U)*polylog(E, V, log(U)) == Space Complexity == $O(E)$ words ((derived in notes)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6979027")
- 10:54, 15 February 2023 Gabow ( Maximum Flow) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE*logU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://www.sciencedirect.com/science/article/pii/002200008590039X")
- 10:54, 15 February 2023 Shiloach ( Maximum Flow) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3}*log(V)$/p) == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM (unclear what type; seems like any could work?) == Year == 1981 == Reference == http://users.umiacs.umd.edu/~vishkin/TEACHING/4CLASS/SV82-maxflow.pdf")
- 10:54, 15 February 2023 Galil ( Maximum Flow) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^({5}/{3})$E^({2}/{3})) == Space Complexity == $O(E)$ words (https://link.springer.com/article/10.1007/BF00264254) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://link.springer.com/article/10.1007/BF00264254")
- 10:54, 15 February 2023 MKM Algorithm ( Maximum Flow) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://eprints.utas.edu.au/160/1/iplFlow.pdf")
- 10:54, 15 February 2023 Parallel Merge Sort - Cole (2) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 10:54, 15 February 2023 Parallel Merge Sort - Cole (1) ( Sorting - Comparison) (hist | edit) [284 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217049")
- 10:54, 15 February 2023 ( Negative Triangle) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.5")
- 10:54, 15 February 2023 Larsen, Williams (follows from Theorem 2.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^({11}/{4})$ / sqrt(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Cell Probe == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 10:54, 15 February 2023 Larsen, Williams (Theorem 1.1) ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / {2}^(Omega(sqrt(log n)$))) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2017 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611974782.142")
- 10:54, 15 February 2023 Williams ( Online Matrix Vector Multiplication (OMV)) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / (log n)$^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == http://www.cs.cmu.edu/~./theorylunch/pastSemesterIndices/slides/20070117.pdf")
- 10:54, 15 February 2023 Yu (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}*poly(log log n)$/log^{4} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = Omega(log n) == Year == 2015 == Reference == https://www.sciencedirect.com/science/article/pii/S0890540118300099")
- 10:54, 15 February 2023 Chan (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{3} / log^{3} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM with word size w = log n == Year == 2015 == Reference == https://epubs.siam.org/doi/abs/10.1137/1.9781611973730.16")
- 10:54, 15 February 2023 Bansal, Williams (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * (log log n)$^{2} / log^{2.25} n) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM with word size w = log n == Year == 2009 == Reference == https://ieeexplore.ieee.org/abstract/document/5438580")
- 10:54, 15 February 2023 Method of Four Russians (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}/(log n)$^{2}) == 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 O'Neil 1973 (Boolean Matrix Multiplication Matrix Product) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1973 == Reference == https://core.ac.uk/download/pdf/82467126.pdf")
- 10:54, 15 February 2023 (Boolean Matrix Multiplication (Combinatorial) Matrix Product) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} / log^{2.25} n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.4")
- 10:54, 15 February 2023 Output-Sensitive Quantum BMM (Boolean Matrix Multiplication Matrix Product) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == O*( \min \{n^{1/3} L^{17/{3}0}, n^{1.5} L^{1/4}\}) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Quantum == Year == 2018 == Reference == https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 1.6")
- 10:54, 15 February 2023 Cygan, Gabow, Sankowski (Bounded integer weights Graph Diameter) (hist | edit) [298 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(M*V^omega*polylog(M, V)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == https://dl.acm.org/doi/abs/10.1145/2736283")
- 10:53, 15 February 2023 Ausiello et al. (Maximum Cut, Approximate Maximum Cut) (hist | edit) [516 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} logE)$ == Space Complexity == $O(V^{2})$? words (Each vertex keeps track of O(V)-sized vector. assuming this is the goemans-williamson algorithm) == Description == == Approximate? == Approximate Approximation Factor: ~0.878; assuming this is the goemans-williamson algorithm == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://link.springer.com/content/pdf/1...")
- 10:53, 15 February 2023 Khuller; Raghavachari & Young, "Greedy Methods" (Maximum Cut, Approximate Maximum Cut) (hist | edit) [484 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://doc.lagout.org/science/0_Computer%20Science/2_Algorithms/Handbook%20of%20Approximation%20Algorithms%20and%20Metaheuristics%20%5BGonzalez%...")
- 10:53, 15 February 2023 Mitzenmacher & Upfal (Maximum Cut, Approximate Maximum Cut) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://lib.ysu.am/open_books/413311.pdf")
- 10:53, 15 February 2023 Motwani & Raghavan (Maximum Cut, Approximate Maximum Cut) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V)$? == Space Complexity == $O(V)$ auxiliary words (Keeps track of current coloring/random assignment) == Description == == Approximate? == Approximate Approximation Factor: 0.5 == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1995 == Reference == https://rajsain.files.wordpress.com/2013/11/randomized-algorithms-motwani-and-raghavan.pdf")
- 10:53, 15 February 2023 Hadlock (Maximum Cut Maximum Cut) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^V)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference ==")
- 10:53, 15 February 2023 Iterative naive (d-Neighborhood of a String d-Neighborhood of a String) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(f_{bin}(sigma-{1}, n, d)$) where f_{bin}(x, y, z) = sum_{i=0}^z C(y, i)*x^i == Space Complexity == $O(n)$ auxiliary words (Keep track of which indices the differing letters are on, along with which set of letters are replacing the letters in these indices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == http://rosalind.info/...")