New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:18, 15 February 2023 Stege, Fellows + Interleaving method (Niedermeier, Rossmanith) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+({1.2906})$^k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://mediatum.ub.tum.de/doc/1094228/file.pdf")
- 11:18, 15 February 2023 Stege, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+max(({1.25542})$^k k^{2}, ({1.2906})^k k) == Space Complexity == $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) words ((see remark in algo id #576)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/69332/eth-4359-01.pdf")
- 11:18, 15 February 2023 Papadimitriou and M Yannakakis 1996 + Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [453 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k k^{2}+kn)$ == Space Complexity == $O(k^{2})$ auxiliary? words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 11:18, 15 February 2023 Downey, Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn+{2}^k k^{2})$ == Space Complexity == $O(k^{2})$ auxiliary words (Auxiliary graph contains O(k^2) edges unless the instance is rejected; rest of steps take O(k) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.2.7270&rep=rep1&type=pdf")
- 11:18, 15 February 2023 Chan (Real 3SUM 3SUM) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2018 == Reference == https://dl.acm.org/doi/abs/10.1145/3363541")
- 11:18, 15 February 2023 Exhaustive search (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(C(n, k)$) (i.e. (n, k) binomial coefficient) == Space Complexity == $O(k)$ auxiliary words (Just need to keep track of current subset being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference ==")
- 11:18, 15 February 2023 Freund (Real 3SUM 3SUM) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}*(log log n)$/(log n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2017 == Reference == https://link.springer.com/article/10.1007/s00453-015-0079-6")
- 11:18, 15 February 2023 Gronlund, Pettie (Real 3SUM 3SUM) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/((log n)$/(log log n))^{2}/{3}) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 2014 == Reference == https://ieeexplore.ieee.org/abstract/document/6979047")
- 11:18, 15 February 2023 Baran, Demaine, Patrascu (Integer 3SUM 3SUM) (hist | edit) [311 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2})) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 2008 == Reference == https://link.springer.com/article/10.1007/s00453-007-9036-3")
- 11:18, 15 February 2023 Kazuhisa Makino, Takeaki Uno; Section 6 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(delta^{4})$ == Space Complexity == $O(n+m)$ auxiliary(?) words (https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/chapter/10.1007/978-3-540-27810-8_23")
- 11:18, 15 February 2023 Textbook Sort-and-Two-Sided-Traversal (Integer 3SUM 3SUM) (hist | edit) [261 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 11:18, 15 February 2023 Textbook Sort-and-Binary-Search (Integer 3SUM 3SUM) (hist | edit) [267 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log n)$ == Space Complexity == $O(n)$ words (Storing sorted list) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == - == Reference == -")
- 11:18, 15 February 2023 Kmett (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(h)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://www.schoolofhaskell.com/user/edwardk/online-lca")
- 11:18, 15 February 2023 Fischer, Heun (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(n)$ words (https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.64.5439")
- 11:18, 15 February 2023 Schieber; Vishkin (Parallel) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+log(n)$) == Space Complexity == $O(n)$ total (auxiliary?) words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")
- 11:18, 15 February 2023 Harel, Tarjan (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e46f9daf65174")
- 11:18, 15 February 2023 Harel, Tarjan (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [487 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://www.semanticscholar.org/paper/Fast-Algorithms-for-Finding-Nearest-Common-Harel-Tarjan/8867d059dda279b1aed4a0301e4e...")
- 11:18, 15 February 2023 Sleator and Tarjan (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 11:18, 15 February 2023 Sleator and Tarjan (Linking and Cutting) (Lowest Common Ancestor with Linking and Cutting Lowest Common Ancestor) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(n)$) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
- 11:18, 15 February 2023 Modified van Leeuwen (Linking Roots) (Lowest Common Ancestor with Linking Roots Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 11:18, 15 February 2023 Modified van Leeuwen (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m*log(log(n)$)) == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == (Unpublished report)")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Static Trees) (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(log(n))) == Space Complexity == $O(n*log(log(n)$)) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Brent-Dekker Method (General Root Computation Root Computation) (hist | edit) [539 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 ==...")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Offline) (Off-Line Lowest Common Ancestor Lowest Common Ancestor) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+ m*alpha(m + n, n)$) where alpha is the inverse Ackermann function == Space Complexity == $O(n)$ words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Aho, Hopcroft, and Ullman (Linking) (Lowest Common Ancestor with Linking Lowest Common Ancestor) (hist | edit) [354 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((m+n)$*log(n)) == Space Complexity == $O(n*log(n)$) words (https://www.cs.bgu.ac.il/~segal/PAPERS2/tarj.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/pdf/10.1145/800125.804056")
- 11:18, 15 February 2023 Inverse quadratic interpolation (General Root Computation Root Computation) (hist | edit) [490 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2} along with function values f_i, f_{i-1}, f_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?)...")
- 11:18, 15 February 2023 Steffensen's method (General Root Computation Root Computation) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store previous estimate x_i; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?) == Reference ==")
- 11:18, 15 February 2023 Householder's Method (Root Computation with continuous derivatives (up to d) Root Computation) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(d*n_max)$? == Space Complexity == $O(d)$ words (Store current estimate x_i and the derivatives f' through f^{(d)} (assuming these take O(1) space each); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940(?...")
- 11:18, 15 February 2023 ITP Method (General Root Computation Root Computation) (hist | edit) [437 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_0+log((b-a)$/epsilon)) == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940? == Reference == -")
- 11:18, 15 February 2023 Anderson–Björck algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1973 == Reference == https://link.springer.com/article/10.1007/BF01951936")
- 11:18, 15 February 2023 Illinois Algorithm (General Root Computation Root Computation) (hist | edit) [470 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_max)$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1971 == Reference == https://link.springer.com/article/10.1007/BF01934364")
- 11:18, 15 February 2023 Gabow, Galil, Spencer (general Maximum-weight matching) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(log(log(n)$/log({2}+m/n))) + n^{2}*log(n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/abstract/document/715935")
- 11:18, 15 February 2023 Galil, Micali, Gabow (general Maximum-weight matching) (hist | edit) [323 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.proquest.com/docview/919855909?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Gabow (general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://www.proquest.com/docview/287948024?pq-origsite=gscholar&fromopenview=true")
- 11:18, 15 February 2023 Johnson (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [341 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn*log(n)$/log({2}+m/n)) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900010")
- 11:18, 15 February 2023 Fredman-Tarjan (Edmonds-Karp-based) (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn+n^{2}log(n)$) == Space Complexity == $O(n^{2})$ words (^see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/28869.28874")
- 11:18, 15 February 2023 Edmonds-Karp (bipartite (i.e. assignment), general Maximum-weight matching) (hist | edit) [581 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*(SP+))$ where $(SP+)$ denotes the time for one SSSP computation on a nonnegatively weighted graph. Initially $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Keeps track of current flow, which is of size O(n^2), and an O(n)-sized labeling function. SSSP computation has time bounded by O(n^2) and thus should use O(n^2) space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Co...")
- 11:18, 15 February 2023 Zaks' prefix reversal algorithm ( All permutations) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ on specific permutations == Space Complexity == $O(n)$ auxiliary (see NEXT algorithm in same paper) words (https://link.springer.com/content/pdf/10.1007/BF01937486.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/article/10.1007/BF01937486")
- 11:18, 15 February 2023 Ives' algorithm c ( All permutations) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n) words needed to keep track of which elements have cycled how many times) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/abs/10.1145/359997.360002")
- 11:18, 15 February 2023 Ord-Smith ( All permutations) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array q (as in paper) necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/362896.362913")
- 11:18, 15 February 2023 Langdon ( All permutations) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ per permutation == Space Complexity == $O({1})$ auxiliary words (Only need the auxiliary variable N, according to the flowchart in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == https://dl.acm.org/doi/pdf/10.1145/363282.363315")
- 11:18, 15 February 2023 Wells ( All permutations) (hist | edit) [367 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1})$ per permutation == Space Complexity == $O(n)$ auxiliary words (O(n)-sized array for t_k's necessary) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.jstor.org/stable/2004229#metadata_info_tab_contents")
- 11:18, 15 February 2023 Divide and Conquer ( Minimum value in each row of an implicitly-defined totally monotone matrix) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*log(n)$) == Space Complexity == $O(log(n)$) auxiliary? words (Need to keep track of the specific indices where the minimums occur, up to depth log(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://link.springer.com/article/10.1007/BF01840359")
- 11:18, 15 February 2023 Micali, Vazirani (general graph Maximum cardinality matching) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{0.5} E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 11:18, 15 February 2023 Blossom Algorithm (general graph Maximum cardinality matching) (hist | edit) [498 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E)$ == Space Complexity == $O(E)$ auxiliary? words (Manipulates a constant number of graphs? Contractions can be kept track of in O(E) space) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1961 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/paths-trees-and-flowers/08B492B72...")
- 11:18, 15 February 2023 Alt, Blum, Mehlhorn, Paul (bipartite graph Maximum cardinality matching) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{1.5}*(E/logV)$^{0.5}) == Space Complexity == $O(E)$ auxiliary? words (Uses constant number of O(E)-sized data structures in pseudocode of algorithm) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == Yes, == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.sciencedirect.com/science/article/pii/002001909190195N")
- 11:18, 15 February 2023 Masek, Paterson (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn/log(n)$) == Space Complexity == $O(mn/log(n)$) words (https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [334 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wagner-Fischer algorithm (Edit distance, constant-size alphabet Sequence Alignment) (hist | edit) [303 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/doi/abs/10.1145/321796.321811")
- 11:18, 15 February 2023 Wu and Manber, Fuzzy String Matching ( String Search) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nk \lceil m/w \rceil)$ == Space Complexity == $O(ms + k \lceil m/w \rceil)$ (https://dl.acm.org/doi/pdf/10.1145/135239.135244) == Description == == Approximate? == Approximate Approximation Factor: Levensthein Distance = k == Randomized? == No, deterministic == Model of Computation == not mentioned == Year == 1992 == Reference == https://dl.acm.org/doi/pdf/10.1145/135239.135244")