New pages

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

• 11:15, 15 February 2023 ‎Boman; Chen; Hendrickson; Toledo (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) ‎[452 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log({1}/ϵ)$ ) == Space Complexity == $O(n)$ words (Derived: The preconditioners used have $O(n)$ non-zero entries) == Description == Maximum-weight-basis (MWB) preconditioners == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.343")
• 11:15, 15 February 2023 ‎Boman; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) ‎[332 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $\tilde{O}(mn^{({1}/{2})})$ == Space Complexity == () == Description == == Approximate? == Approximate Approximation Factor: \epsilon == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://epubs.siam.org/doi/10.1137/S0895479801390637")
• 11:15, 15 February 2023 ‎Bern; Gilbert; Hendrickson (Inexact Laplacian Solver SDD Systems Solvers) (hist | edit) ‎[304 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == () == Description == Support Graph Preconditioning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=1117896")
• 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")

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