New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:15, 15 February 2023 Spielman, Teng (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [556 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m log^c n)$ == Space Complexity == $O(n)$ words (Derived: Uses spanning trees and sparse Cholesky factorization which both take $O(n)$ space) == Description == Spectral Sparsification == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/doi/pdf/10.1145/1007352.1007372?casa_token=k60CrC_UJp0AA...")
- 11:15, 15 February 2023 Chan-Singhal-Liu ( Mutual Exclusion) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process seems to keep track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1990 == Reference == https://ieeexplore.ieee.org/document/113817")
- 11:15, 15 February 2023 Peterson's algorithm ( Mutual Exclusion) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ total communication variables? (see original paper ("requires $2n-1$ shared variables of size $n$")) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf")
- 11:15, 15 February 2023 Vaidya (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{({3}/{4})$}) == Space Complexity == $O(n)$ words (Derived: Uses a spanning tree (size $O(n)$)) == Description == Using maximum-weight spanning trees == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference ==")
- 11:15, 15 February 2023 Naimi-Trehel's algorithm ( Mutual Exclusion) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O({1})$ per process, $O(n)$ total? communication variables? (Each process keeps track of a constant number of variables (see algorithm descriiption)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0743731596900416")
- 11:14, 15 February 2023 Dekker's algorithm (2-thread Mutual Exclusion Mutual Exclusion) (hist | edit) [246 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == communication variables? () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1963 == Reference == -")
- 11:14, 15 February 2023 Elliptic-curve Diffie-Hellman (ECDH) (Key Exchange Key Exchange) (hist | edit) [452 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n^{2})? where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 2006 == Reference == https://csrc.nist.gov/publications/detail/sp/800-56a/revised/archive/2007-03-14")
- 11:14, 15 February 2023 Diffie–Hellman key exchange (Key Exchange Key Exchange) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mult(n)$*n) where mult(n) is running time on n-bit multiplication == Space Complexity == $O(n)$ bits (Each party only keeps track of a constant number of n-bit integers) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1055638")
- 11:14, 15 February 2023 Klein (section 5) (Planar Bipartite Graph Perfect Matching Maximum Cardinality Matching) (hist | edit) [532 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{({4}/{3})$} logV) == Space Complexity == $O(V^{({4}/{3})$})? words (Considers and operates on a graph partition (which still takes up $O(E)=O(V)$ space), and computes shortest-path distances within each graph partition, the total of which requires $O(V^{(4/3)})$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == http:...")
- 11:14, 15 February 2023 Mucha, Sankowski (general) (General Graph MCM Maximum Cardinality Matching) (hist | edit) [365 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2.{37}6})$ == Space Complexity == $O(V^{2})$?? words (Algorithm uses/manipulates constant number of matrices and graphs?) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2004 == Reference == https://ieeexplore.ieee.org/document/1366244")
- 11:14, 15 February 2023 Gabow; Tarjan (General Graph MCM Maximum Cardinality Matching) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary? words (https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf")
- 11:14, 15 February 2023 Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [416 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) == Space Complexity == $O(E)$ auxiliary?? words (Designs a flow network and runs pseudoflow algorithms on graph; space can be reused if too many residual graphs are created) == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/abs/1105.1569")
- 11:14, 15 February 2023 Blum (General Graph MCM Maximum Cardinality Matching) (hist | edit) [436 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(E)$ auxiliary?? words (Each phase, creates a separate directed graph and solves a reachability problem on it. Can reuse space across phases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf")
- 11:14, 15 February 2023 Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [443 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{10/7}*polylog(V)$) == Space Complexity == $O(E + V)$ words (Derived: Uses an augmented graph (copy of the original graph plus an additional node with edges between it and all other nodes)) == Description == Based on electric flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://arxiv.org/abs/1307.2205")
- 11:14, 15 February 2023 Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [422 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O((V^{0.5})$E) == Space Complexity == $O(V)$ auxiliary words (maximal set of vertex-disjoint shortest augmenting paths uses O(V) space to store, taking symmetric difference also uses O(V) space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://epubs.siam.org/doi/10.1137/0202019")
- 11:14, 15 February 2023 Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [550 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication == Space Complexity == $O(VlogV)$??? words (Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2006 == Re...")
- 11:14, 15 February 2023 Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching) (hist | edit) [456 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(E)$ auxiliary words (creating new graph and using it as input to the Ford-Fulkerson algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764")
- 11:14, 15 February 2023 Hash join ( Joins) (hist | edit) [285 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n+m)$? words (Need a hash table of at least that size) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Sort merge join ( Joins) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn + mlogm)$ == Space Complexity == $O(n+m)$? words (Need sorted lists of indices of input tables) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Nested loop join ( Joins) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ == Space Complexity == $O({1})$ words (Just need to keep track of which rows are being checked) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM(?) == Year == 1960 == Reference == -")
- 11:14, 15 February 2023 Basic Local Alignment Search Tool (BLAST) (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2231712")
- 11:14, 15 February 2023 Gapped BLAST (Edit Sequence, constant-size alphabet Sequence Alignment) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$? words (Uses at most a constant number of O(m)*O(n) arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/9254694")
- 11:14, 15 February 2023 Apostolico–Giancarlo Algorithm (Single String Search String Search) (hist | edit) [440 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m + s)$ + $O(n)$ == Space Complexity == $O(m)$ words (https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1) == Description == Variant of BM == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1456&context=cstech&sei-redir=1")
- 11:14, 15 February 2023 Boyer-Moore-Horspool (BMH) (Single String Search String Search) (hist | edit) [386 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Bad-character heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380100608")
- 11:14, 15 February 2023 BOM (Backward Oracle Matching) (Single String Search String Search) (hist | edit) [396 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m)$ + $O(mn)$ == Space Complexity == $O(m)$ words (https://link.springer.com/content/pdf/10.1007/3-540-47849-3_18.pdf) == Description == Automaton-based oracle == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-47849-3_18")
- 11:14, 15 February 2023 Raita Algorithm (Single String Search String Search) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (Derived: Uses a bad-character shift table of size $O(s)$) == Description == Slight variation of BMH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://www.cin.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf")
- 11:14, 15 February 2023 Aho–Corasick (AC) Algorithm (Multiple String Search String Search) (hist | edit) [410 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m + z)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, finite automaton that tracks the partial prefix match == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://cr.yp.to/bib/1975/aho.pdf")
- 11:14, 15 February 2023 Commentz-Walter Algorithm (Multiple String Search String Search) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(km)$ words (Derived: Number of states of the automaton that is created) == Description == Automaton-based, constructs a converse state machine from the given patterns == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == https://link.springer.com/chapter/10.1007/3-540-09510-1_10")
- 11:14, 15 February 2023 Backward Non-Deterministic DAWG Matching (BNDM) (Single String Search String Search) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(sm)$ words (https://link.springer.com/chapter/10.1007/BFb0030778) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://link.springer.com/chapter/10.1007/BFb0030778")
- 11:14, 15 February 2023 Fast Hybrid Algorithm (Single String Search String Search) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$+ $O(m+s)$ == Space Complexity == $O(m)$ words (Derived: Uses three tables, each of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://thesai.org/Downloads/Volume8No6/Paper_15-Fast_Hybrid_String_Matching_Algorithm.pdf")
- 11:14, 15 February 2023 Quick-Skip Searching (Single String Search String Search) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses two tables, both of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2012 == Reference == http://www.ijcte.org/papers/462-G1278.pdf")
- 11:14, 15 February 2023 String-Matching with Finite Automata (Single String Search String Search) (hist | edit) [275 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: $O(m)$ states in the DFA) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 11:14, 15 February 2023 Two-way String-Matching Algorithm (Single String Search String Search) (hist | edit) [364 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n + m)$ == Space Complexity == $O({1})$ words (http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf")
- 11:14, 15 February 2023 Shor's algorithm Quantum Implementation (Second Category Integer Factoring Integer Factoring) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ qubits (https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 1994 == Reference == https://ieeexplore.ieee.org/document/365700/")
- 11:14, 15 February 2023 General number field sieve (Second Category Integer Factoring Integer Factoring) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({64}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1996 == Reference == http://www.ams.org/notices/199612/pomerance.pdf")
- 11:14, 15 February 2023 Special number field sieve (First Category Integer Factoring Integer Factoring) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(exp(({1}+o({1})$)({32}n/{9})^{({1}/{3})}(log n)^{({2}/{3})}) heuristically? == Space Complexity == $O(n^{2/3})$ bits (http://www.ams.org/notices/199612/pomerance.pdf) == Description == For integers of the form $r^e \pm s$, for r and s relatively small == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
- 11:14, 15 February 2023 Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [467 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log(V)$/p) == Space Complexity == $O(V)$ total words (Initializes and uses a constant number of arrays of size O(V) (and does work similar to work done in Boruvka/Prim algorithm)) == Description == Parallel algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAM/SMPs? == Year == 2006 == Reference == https://www.sciencedirect.com/science/article/pii/S0743731506001262")
- 11:14, 15 February 2023 Incremental convex hull algorithm; Michael Kallay ( Convex Hull) (hist | edit) [294 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == https://www.sciencedirect.com/science/article/pii/002001908490084X")
- 11:14, 15 February 2023 Alon and Kahale (3-Graph Coloring Graph Coloring) (hist | edit) [279 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.24}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://www.cs.tau.ac.il/~nogaa/PDFS/spectcolpr1.pdf")
- 11:14, 15 February 2023 Johnson (3-Graph Coloring Graph Coloring) (hist | edit) [300 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.4422}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1988 == Reference == https://www.sciencedirect.com/science/article/abs/pii/0020019088900658")
- 11:14, 15 February 2023 Hirsch (3-Graph Coloring Graph Coloring) (hist | edit) [273 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.239}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1998 == Reference == https://dl.acm.org/doi/10.5555/314613.314838")
- 11:14, 15 February 2023 Schöning (3-Graph Coloring Graph Coloring) (hist | edit) [260 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.333}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == Yes, == Model of Computation == == Year == 1999 == Reference == https://ieeexplore.ieee.org/document/814612")
- 11:14, 15 February 2023 Robson (3-Graph Coloring Graph Coloring) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2108}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900325")
- 11:14, 15 February 2023 Wu et al. (LCS Longest Common Subsequence) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$? words (Derived: Same as the above two) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://publications.mpi-cbg.de/Wu_1990_6334.pdf")
- 11:14, 15 February 2023 Ahuja et al. ( Maximum Flow) (hist | edit) [326 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELog(V(LogU)$^{0.5} / E)) == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1987 == Reference == http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.5093&rep=rep1&type=pdf")
- 11:14, 15 February 2023 Miller and Myers (LCS Longest Common Subsequence) (hist | edit) [393 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (Derived: Uses an upper triangular matrix $M$ that is size $(m + 1) \times (m + 1)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/spe.4380151102")
- 11:14, 15 February 2023 Nakatsu et al. (LCS Longest Common Subsequence) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(m-r)$) == Space Complexity == $O(m^{2})$ words (https://link.springer.com/content/pdf/10.1007/3-540-58338-6_63.pdf, Fig. 3) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://link.springer.com/article/10.1007/BF00264437")
- 11:09, 15 February 2023 List:Algorithms (hist | edit) [281,464 bytes] Admin (talk | contribs) (Created page with "{| class="wikitable sortable" style="text-align:center;" width="100%" ! Family !! Name !! Year !! Time Complexity !! Space Complexity |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Melhorn's Approximation algorithm (Approximate OBST Optimal Binary Search Trees) || 1975 || $O(n)$ || $O(n)$ |- | style="text-align:left;" | Approximate OBST || style="text-align:left;" | Karpinski (Appro...")
- 10:55, 15 February 2023 Reduction from MAX-CNF-SAT to Maximum Local Edge Connectivity (hist | edit) [480 bytes] Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: Maximum Local Edge Connectivity == Description == == Implications == assume: SETH<br/>then: for any $\epsilon > {0}$, in graphs with $n$ nodes and $\tilde{O}(n)$ edges, target cannot be solved in time $O(n^{2-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https://dl.acm.org/doi/abs/10.1145/32...")
- 10:55, 15 February 2023 Reduction from MAX-CNF-SAT to All-Pairs Maximum Flow (hist | edit) [602 bytes] Admin (talk | contribs) (Created page with "FROM: MAX-CNF-SAT TO: All-Pairs Maximum Flow == Description == == Implications == assume: SETH<br/>then: for any fixed $\epsilon > {0}$, in graphs with $n$ nodes, $m=O(n)$ edges, and capacities in $\{1,\cdots,n\}$ target cannot be solved in time $O((n^{2}m)^{1-\epsilon})$ == Year == 2018 == Reference == Krauthgamer, R., & Trabelsi, O. (2018). Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4), 1-15. https:/...")