New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:16, 15 February 2023 Gusfield (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [537 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it pre-processes and stores the string and the reverse of the string, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://www.cambridge.org/core/books/al...")
- 11:16, 15 February 2023 Jeuring (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary? words (Stores (and uses) previously computed palindrome information; unclear if O(n) is best bound possible) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://doi.org/10.1007%2FBF01182773")
- 11:16, 15 February 2023 Manacher (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ auxiliary words (At the very least it stores the radii for each center, requiring O(n) space. Space usage is bounded from above by runtime, so at most O(n) space is used.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://doi.org/10.1145%2F321892.321896")
- 11:16, 15 February 2023 Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1953 == Reference == -")
- 11:16, 15 February 2023 Naive (Longest Palindromic Substring Longest Palindromic Substring) (hist | edit) [312 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ auxiliary words (https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 11:16, 15 February 2023 Record linking (Entity Resolution Entity Resolution) (hist | edit) [223 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference ==")
- 11:16, 15 February 2023 Ananthakrishna (Entity Resolution Entity Resolution) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(n)$ words (Derived: the token table, the children table, and the tuples in G are stored in main memory, each are of size $O(n)$) == Description == Delphi algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://doi.org/10.1016/B978-155860869-6/50058-5")
- 11:16, 15 February 2023 Bellare Active Learning (Entity Resolution Entity Resolution) (hist | edit) [327 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn clogc)$ == Space Complexity == () == Description == Pairwise ER Active Learning == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2012 == Reference == https://dl.acm.org/doi/10.1145/2339530.2339707")
- 11:16, 15 February 2023 EM Based Winkler (Entity Resolution Entity Resolution) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://courses.cs.washington.edu/courses/cse590q/04au/papers/WinklerEM.pdf")
- 11:16, 15 February 2023 Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} k)$ == Space Complexity == $O(k)$ words (Derived: One value per feature in the discretized vector) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://arxiv.org/abs/1207.4180")
- 11:16, 15 February 2023 Chen Ensembles of classifiers (Entity Resolution Entity Resolution) (hist | edit) [242 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference ==")
- 11:16, 15 February 2023 Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) (hist | edit) [428 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == Bipartite method to compute pairwise ER == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2009 == Reference == https://doi.org/10.14778/1687627.1687661")
- 11:16, 15 February 2023 Fellegi & Sunter Model (Entity Resolution Entity Resolution) (hist | edit) [450 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == https://www.tandfonline.com/doi/abs/10.1080/01621459.1969.10501049")
- 11:16, 15 February 2023 Rytter (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [472 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(logn)$ == Space Complexity == $O(n)$ words (https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 2004 == Reference == https://www.researchgate.net/publication/228945502_On_parallel_transformations_of_suffix_arrays_into_suffix_trees")
- 11:16, 15 February 2023 McCreight (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == http://libeccio.di.unisa.it/TdP/suffix.pdf")
- 11:16, 15 February 2023 Farach (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log n)$ == Space Complexity == $O(n)$ words (https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == CRCW PRAM == Year == 1997 == Reference == https://www.cs.rutgers.edu/~farach/pubs/PRAMSuffixICALP.pdf")
- 11:16, 15 February 2023 Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [415 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{2}(n)$) == Space Complexity == $O(n^{({1}+\eps)})$ for any fixed eps>{0} words (https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CRCW PRAM == Year == 1994 == Reference == https://link.springer.com/content/pdf/10.1007/3-540-57811-0_3.pdf")
- 11:16, 15 February 2023 Hariharan (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [384 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(log^{4}(n)$) == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/S0022000097914963) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1997 == Reference == https://www.sciencedirect.com/science/article/pii/S0022000097914963")
- 11:16, 15 February 2023 Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (https://link.springer.com/article/10.1007/BF01769703) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://link.springer.com/article/10.1007/BF01769703")
- 11:16, 15 February 2023 Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [391 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf")
- 11:16, 15 February 2023 Pratt (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [235 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
- 11:16, 15 February 2023 Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [376 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/citation.cfm?id=1441766")
- 11:16, 15 February 2023 Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{3})$ words (https://link.springer.com/content/pdf/10.1007/s00453-010-9411-3.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://community.dur.ac.uk/george.mertzios/papers/Conf/Conf_Longest-Interval.pdf")
- 11:16, 15 February 2023 Naive (Constructing Suffix Trees Constructing Suffix Trees) (hist | edit) [339 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words (Needs to store the intermediate steps of constructing a suffix tree, which can reach size O(n)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -")
- 11:16, 15 February 2023 Patrick Posser (Stable Roommates Problem Stable Matching Problem) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n)$ words (https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == https://link.springer.com/chapter/10.1007%2F978-3-319-07046-9_2")
- 11:16, 15 February 2023 S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ per processor? words (Only need to keep track of current (provisional) matchings) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://link.springer.com/content/pdf/10.1007/BF02136029.pdf")
- 11:16, 15 February 2023 Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) (hist | edit) [409 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? (see original reference)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2005 == Reference == http://www.dcs.gla.ac.uk/~pat/roommates/distribution/papers/SM2N.pdf")
- 11:16, 15 February 2023 Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) (hist | edit) [372 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 == 2001 == Reference == https://link.springer.com/chapter/10.1007/3-540-45578-7_16")
- 11:16, 15 February 2023 Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$ words (Derived: Storing the inverse of the Laplacian) == Description == Use Gaussian elimination to compute the inverse of the Laplacian to solve for x == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == -150 == Reference == -")
- 11:15, 15 February 2023 9-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1978 == Reference ==")
- 11:15, 15 February 2023 5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1970 == Reference ==")
- 11:15, 15 February 2023 9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1969 == Reference ==")
- 11:15, 15 February 2023 5-point FFT (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [317 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (FFT generally requires aux. space equal to dimension of vector?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 11:15, 15 February 2023 9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1965 == Reference ==")
- 11:15, 15 February 2023 9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1964 == Reference == https://epubs.siam.org/doi/pdf/10.1137/0113067")
- 11:15, 15 February 2023 9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [322 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1956 == Reference ==")
- 11:15, 15 February 2023 5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2} log^{2}n)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1955 == Reference ==")
- 11:15, 15 February 2023 5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [329 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == $O(n^{2})$? words (Need one auxiliary O(n^2)-sized vector to store guess, and the scalar sigma) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1954 == Reference ==")
- 11:15, 15 February 2023 5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4} logn)$ == Space Complexity == $O(n^{2})$? words (Generally uses a constant number of n^2*n^2 matrices where O(n^2) entries are nonempty) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:15, 15 February 2023 5-point Gauss elimination (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [305 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{4})$ words (See Gauss-Jordan elimination, but matrix is of size n^2*n^2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:15, 15 February 2023 5-point star Cramer's rule (2-Dimensional Poisson Problem Poisson Problem) (hist | edit) [463 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({4}^{(n^{2})})$ == Space Complexity == $O({4}^{(n^{2})})$ for sure, $O(n^{2})$ possibly??? (if super conservative) words (For expansion by minors, each "level" of expansion requires computing and storing O(1) smaller determinants, and there are O(n^2) levels overall) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM? == Year == 1945 == Reference ==")
- 11:15, 15 February 2023 TSPLIB (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [304 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^V logE)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://pubsonline.informs.org/doi/abs/10.1287/ijoc.3.4.376")
- 11:15, 15 February 2023 Lawler; E. L. (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [306 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.674}^V E^{2})$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://onlinelibrary.wiley.com/doi/10.1002/net.3230180309")
- 11:15, 15 February 2023 Christofides algorithm (Approximate TSP The Traveling-Salesman Problem) (hist | edit) [458 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3})$ == Space Complexity == $O(V^{2})$??? words (Depends on best space complexity for O(V^3) min-weight matching (the rest of the algorithm requires O(V) auxiliary space)) == Description == == Approximate? == Approximate Approximation Factor: 1.5 == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf")
- 11:15, 15 February 2023 Held–Karp algorithm (Minimum TSP The Traveling-Salesman Problem) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} {2}^V)$ == Space Complexity == $O(V*{2}^V)$ words (Need to store all C(S, l) for all subsets $S \subseteq V$ and all vertices l) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == https://www.jstor.org/stable/2098806")
- 11:15, 15 February 2023 Kazuhisa Makino, Takeaki Uno; Section 5 (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [441 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{\omega})$ per clique where omega is the exponent on matrix multiplication == Space Complexity == $O(n^{2})$ 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:15, 15 February 2023 Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [473 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nm)$ per clique == Space Complexity == $O(m)$ auxiliary words (See original reference, but also note that we'd have to construct and store the complementary graph (as this is originally an algo for MISs)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.proquest.com/docview/918487776?pq-origsite=gscholar&fromopenv...")
- 11:15, 15 February 2023 M. Chrobak and D. Eppstein (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [432 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n d^{2} {2}^d)$ == Space Complexity == $O(n)$ auxiliary? words (Keeps track of degeneracy ordering along with vertex and subset being tested (here the subset size is bounded by O(d)=O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.ics.uci.edu/~eppstein/pubs/ChrEpp-TCS-91.pdf")
- 11:15, 15 February 2023 Chiba and Nishizeki (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [412 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(a(G)*m)$ per clique == Space Complexity == $O(m)$ auxiliary words (https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://pdfs.semanticscholar.org/0d19/245a27bc65a87a8014d5b8a66fb514c8ff0b.pdf")
- 11:15, 15 February 2023 David Eppstein, Maarten Löffler, Darren Strash (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(dn {3}^{(d/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch, but also keeps track of O(n)-sized degeneracy ordering) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2010 == Reference == https://arxiv.org/pdf/1006.5440.pdf")