New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:53, 15 February 2023 SHEFFER A.; LÉVY B.; MOGILNITSKY M.; BOGOMYAKOV A. 2005 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://hal.inria.fr/inria-00105689/document")
- 10:53, 15 February 2023 SHEFFER A.; DE STURLER E. 2000 (Mesh Parameterization Mesh Parameterization) (hist | edit) [277 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://link.springer.com/article/10.1007/PL00013391")
- 10:53, 15 February 2023 HORMANN K.; GREINER G 1999 (Mesh Parameterization Mesh Parameterization) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1999 == Reference == https://www.semanticscholar.org/paper/MIPS%3A-An-Efficient-Global-Parametrization-Method-Hormann-Greiner/a2f7f69b37565eb2729b45a7d72c6aae2e4908b8")
- 10:53, 15 February 2023 KARNI Z.; GOTSMAN C.; GORTLER S. J. 2005 (Mesh Parameterization Mesh Parameterization) (hist | edit) [324 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://dash.harvard.edu/bitstream/handle/1/2634388/Gortler_FreeBoundary.pdf?sequence=2&isAllowed=y")
- 10:53, 15 February 2023 LÉVY B.; PETITJEAN S.; RAY N.; MAILLOT J 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log^{2.5} n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://members.loria.fr/Bruno.Levy/papers/LSCM_SIGGRAPH_2002.pdf")
- 10:53, 15 February 2023 DESBRUN M.; MEYER M.; ALLIEZ P. 2002 (Mesh Parameterization Mesh Parameterization) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://dl.acm.org/doi/10.1145/566654.566588")
- 10:53, 15 February 2023 FLOATER 2003 (Mesh Parameterization Mesh Parameterization) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2003 == Reference == https://www.ams.org/journals/mcom/2003-72-242/S0025-5718-02-01466-7/S0025-5718-02-01466-7.pdf")
- 10:53, 15 February 2023 Hentenryck et. al. (Arc Consistency? Stable Matching Problem) (hist | edit) [389 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$? words (https://www.sciencedirect.com/science/article/abs/pii/000437029290020X) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/abs/pii/000437029290020X")
- 10:53, 15 February 2023 Manlove; Malley (Stable Marriage Problem Stable Matching Problem) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Constructs, preprocesses, and solves an $O(n^2)$-size CSP instance?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~davidm/pubs/7981.pdf")
- 10:53, 15 February 2023 Irving's Algorithm (Stable Roommates Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Manipulates the $O(n)$-many $O(n)$-size preference lists) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/roommates/papers/Comp_sdarticle.pdf")
- 10:53, 15 February 2023 Gale–Shapley algorithm (Stable Marriage Problem Stable Matching Problem) (hist | edit) [374 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf")
- 10:53, 15 February 2023 Berlekamp–Massey algorithm (Cryptanalysis of Linear Feedback Shift Registers Cryptanalysis of Linear Feedback Shift Registers) (hist | edit) [356 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(N)$? words (Computes and stores constant number of polynomials of degree $O(N)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1054260")
- 10:53, 15 February 2023 Victor Shoup's algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [517 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is $O(n)$ so the total number of terms to keep track of is $O(n)$. Also, polynomials in the separating set can be computed in $O(n)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.co...")
- 10:53, 15 February 2023 Cantor–Zassenhaus algorithm (Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [523 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Keeps track of a set of factors, where sum of degrees of factors is O(n) so the total number of terms to keep track of is O(n). Also, computing h^{((q^d-1)/2)}-1 mod f only requires O(n) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.ams.org/journals/mcom/1...")
- 10:53, 15 February 2023 Distinct-degree factorization (Distinct-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [420 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} + nlogn)$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration. Note that computing $gcd(f, x^{(q^i)}-x)$ can be cleverly done in $O(n)$ space.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1944 == Reference == -")
- 10:53, 15 February 2023 Schubert's algorithm ( Factorization of Polynomials Over Finite Fields) (hist | edit) [245 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 10:53, 15 February 2023 Square-free factorization (Square-free Factorization of Polynomials Over Finite Fields) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (Computes and stores a constant number of polynomials of degree $O(n)$ per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == -")
- 10:53, 15 February 2023 Berlekamp's algorithm (Distinct-degree; Equal-degree Factorization of Polynomials Over Finite Fields) (hist | edit) [394 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n)$ words (Computes the remainder of $g^{((p-1)/2)}-1 mod f$ (in order to find gcd of $g^{((p-1)/2)}-1$ and f)) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1967 == Reference == https://ieeexplore.ieee.org/document/6768643/")
- 10:53, 15 February 2023 Korada and R. Urbanke; (Lossy Compression Data Compression) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == $O(N)$ words (Derived: size of the polar codes that need to be stored) == Description == Polar codes == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/0903.0307.pdf")
- 10:53, 15 February 2023 Jalali; A. Montanari; and T. Weissman (Lossy Compression Data Compression) (hist | edit) [448 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://authors.library.caltech.edu/17983/1/Jalali2010p7459Ieee_T_Inform_Theory.pdf")
- 10:53, 15 February 2023 Jalali and T. Weissman (Lossy Compression Data Compression) (hist | edit) [497 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$? words (Derived: Auxiliary data structures are H_k and m_k. H_k is just a singular value and is constant space, but m_k is a O(n)-size vector.) == Description == Gibbs sampler == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2008 == Reference == https://web.stanford.edu/~tsachy/pdf_files/Lossy%20Source%20Coding%20via%20Markov%20Cha...")
- 10:53, 15 February 2023 Martinian and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [397 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://arxiv.org/abs/cs/0602046")
- 10:53, 15 February 2023 Miyake 2006 (Lossy Compression Data Compression) (hist | edit) [483 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://www.semanticscholar.org/paper/Lossy-Data-Compression-over-Zq-by-LDPC-Code-Miyake/652f0438118898b63126f7261ec4cd2002ff0e0b")
- 10:53, 15 February 2023 Brute force (Lossy Compression Data Compression) (hist | edit) [288 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference ==")
- 10:53, 15 February 2023 Matsunaga; Yamamoto (Lossy Compression Data Compression) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == exp(n) words (https://doi.org/10.1109/TIT.2003.815805) == Description == Low Density Parity Check (LDPC) == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://doi.org/10.1109/TIT.2003.815805")
- 10:53, 15 February 2023 Ciliberti; Mézard (Lossy Compression Data Compression) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == () == Description == Constraint Satisfaction Problem with Random Gates == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://arxiv.org/abs/cond-mat/0504509")
- 10:53, 15 February 2023 Sun; M. Shao; J. Chen; K. Wong; and X. Wu (Lossy Compression Data Compression) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*{2}^n)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == https://ieeexplore.ieee.org/document/5474629/")
- 10:53, 15 February 2023 Maneva and M. J. Wainwright (Lossy Compression Data Compression) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ bits (Derived: size of the factor graph representation of the generator matrix, or size of the generator matrix itself) == Description == Low Density Generator Matrix (LDGM) codes; for a Bernouli(1/2) source == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://ieeexplore.ieee.org/document/1523592")
- 10:53, 15 February 2023 Discrete Cosine Transform (Lossy Compression Data Compression) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Derived: store the DCT coefficient for each input term) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://doi.org/10.1109%2FT-C.1974.223784")
- 10:53, 15 February 2023 Gupta; Verdu (Lossy Compression Data Compression) (hist | edit) [449 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{3} n)$ == Space Complexity == $O(n)$ bits (Derived: Considering the codebook to be part of the input, this only requires storing a single codeword in memory, of size $O(n)$, along with some constants) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://doi.org/10.1109/TIT.2009.2016040")
- 10:53, 15 February 2023 The Multistage Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 10:53, 15 February 2023 The Multihash Algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [366 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == http://ilpubs.stanford.edu:8090/423/")
- 10:53, 15 February 2023 A-Priori algorithm (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [336 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://dl.acm.org/doi/pdf/10.1145/1014052.1014091) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == http://www.vldb.org/conf/1994/P487.PDF")
- 10:53, 15 February 2023 The Algorithm of Park; Chen; and Yu (PCY) (Finding Frequent Itemsets Finding Frequent Itemsets) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: modification of the Apriori algorithm, with same asymptotic complexities.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://dl.acm.org/doi/abs/10.1145/568271.223813")
- 10:53, 15 February 2023 GLR parser (CFG Parsing CFG Problems) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/978-3-662-21545-6.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? (implemented on ALGOL) == Year == 1974 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-662-21545-6_18")
- 10:53, 15 February 2023 Earley parser (CFG Parsing CFG Problems) (hist | edit) [526 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1968 == Reference == https://web.archive.org/web/20040708052627/http://www-2.cs.cmu.edu/afs/cs.cmu.edu/projec...")
- 10:53, 15 February 2023 Cocke–Younger–Kasami algorithm (CFG Recognition CFG Problems) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} * |G|)$ == Space Complexity == $O(n^{2})$ cells (https://core.ac.uk/download/pdf/158319955.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Double-tape TM == Year == 1968 == Reference == https://core.ac.uk/download/pdf/158319955.pdf")
- 10:53, 15 February 2023 Valiant (CFG Recognition CFG Problems) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^omega * |G|)$ where omega is the exponent for matrix multiplication == Space Complexity == $O(n^{2})$? words/cells (See matrix multiplication space complexity) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM and multitape TM == Year == 1975 == Reference == https://linkinghub.elsevier.com/retrieve/pii/S0022000075800468")
- 10:53, 15 February 2023 Niedermeier, Rossmanith (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.29175}^k k^{2})$. == 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://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.1933&rep=rep1&type=pdf")
- 10:53, 15 February 2023 Downey (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [414 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {1.31951}^k k^{2})$ == 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 == 1998 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.4079&rep=rep1&type=pdf")
- 10:53, 15 February 2023 Papadimitriou and M Yannakakis (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^k n)$ == Space Complexity == $O(k)$ auxiliary? words (keep track of maximal matching, and subsequent vertices in cover; note that max size is O(k) else we can reject immediately) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000096900586")
- 10:53, 15 February 2023 Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [369 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.2738}^k+ kn)$ == Space Complexity == $O(poly(n))$ words (https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://www.cs.lafayette.edu/~gexia/research/mfcs06.pdf")
- 10:53, 15 February 2023 Balasubramanian; Fellows (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + ({1.324718})$^k * k^{2}) == 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 == 1996 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.711.8844")
- 10:53, 15 February 2023 J. Chen; L. Liu; and W. Jia. (The Vertex Cover Problem, Degrees Bounded By 3 The Vertex Cover Problem) (hist | edit) [419 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(k*{1.2192}^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://onlinelibrary.wiley.com/doi/abs/10.1002/1097-0037(200007)35:4%3C253::AID-NET3%3E3.0.CO;2-K")
- 10:53, 15 February 2023 Chandran and F. Grandoni (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [514 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ == Space Complexity == $O(min({1.2759}^k k^{1.5}, {1.2745}^k k^{4}) + kn)$ but exponential words (https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.4409&rep=rep1&type=pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://citeseerx.ist.psu.edu/viewdoc/downloa...")
- 10:53, 15 February 2023 Sam Buss (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [447 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn + {2}^k k^{({2}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^2) auxiliary space at most) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == http://bud.cs.uky.edu/~goldsmit/papers/NondetWithinP.pdf")
- 10:53, 15 February 2023 Brute force (backtracking search) (The Vertex Cover Problem The Vertex Cover Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^k n^O({1})$) == 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 ==")
- 10:53, 15 February 2023 C-LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See LOOK) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 LOOK (Disk Scheduling Disk Scheduling) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (Needs sorted array of requests and seek distance but not much else) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")
- 10:53, 15 February 2023 C-SCAN (Disk Scheduling Disk Scheduling) (hist | edit) [256 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$ auxiliary words (See SCAN) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1979 == Reference == -")