User contributions for Admin

15 February 2023

• 11:1611:16, 15 February 2023 diff hist +342‎ N Babai ( Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == {2}^{$O(\log n)$^3} == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2017 == Reference == http://people.cs.uchicago.edu/~laci/update.html, http://people.cs.uchicago.edu/~laci/17groups/version2.1.pdf" current
• 11:1611:16, 15 February 2023 diff hist +259‎ N Ullman (Subgraph Isomorphism Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321921.321925" current
• 11:1611:16, 15 February 2023 diff hist +307‎ N Schmidt & Druffel ( Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == $O(n*n!)$ == Space Complexity == $O(n^{2})$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://dl.acm.org/doi/10.1145/321958.321963" current
• 11:1611:16, 15 February 2023 diff hist +315‎ N Spielman (Isomorphism of strongly regular graphs Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == $n^{O(n^{({1}/{3})} log n)}$ == Space Complexity == check words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://www.cs.yale.edu/homes/spielman/PAPERS/srg.pdf" current
• 11:1611:16, 15 February 2023 diff hist +338‎ N McKay ( Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == $O((m1 + m2)n^{3} + m2 n^{2} L)$ == Space Complexity == ${2}mn+{10}n+m+(m+{4})K+{2}mL$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf" current
• 11:1611:16, 15 February 2023 diff hist +298‎ N Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == o(\exp({2}n^{1/2}\log^{2}n)) == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://epubs.siam.org/doi/10.1137/0209018"
• 11:1611:16, 15 February 2023 diff hist +349‎ N Babai and Luks (Graph Isomorphism, General Graphs Graph Isomorphism Problem) ‎ Created page with "== Time Complexity == \exp(n^{\frac{1}{2} + o({1})}) == Space Complexity == words () == Description == Construct canonical forms of graphs and compare == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://dl.acm.org/doi/10.1145/800061.808746" current
• 11:1611:16, 15 February 2023 diff hist +368‎ N Sethi–Ullman Algorithm (Arithmetic Expression Binary Tree AST to Code Translation) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ words (Derived: Only uses in-situ updates to the input tree, no auxiliary data structures) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://dl.acm.org/doi/10.1145/321607.321620" current
• 11:1611:16, 15 February 2023 diff hist +401‎ N Demand-Driven Register Allocation (Global Register Allocation Register Allocation) ‎ Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Derived: Requires storing a so-called $\Delta$-table of size $n \times n$ to keep track of $\Delta$-estimates) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236114.236117" current
• 11:1611:16, 15 February 2023 diff hist +547‎ N Gusfield (Longest Palindromic Substring Longest Palindromic Substring) ‎ 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:1611:16, 15 February 2023 diff hist +387‎ N Jeuring (Longest Palindromic Substring Longest Palindromic Substring) ‎ 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:1611:16, 15 February 2023 diff hist +442‎ N Manacher (Longest Palindromic Substring Longest Palindromic Substring) ‎ 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:1611:16, 15 February 2023 diff hist +314‎ N Dynamic Programming (Longest Palindromic Substring Longest Palindromic Substring) ‎ 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 == -" current
• 11:1611:16, 15 February 2023 diff hist +322‎ N Naive (Longest Palindromic Substring Longest Palindromic Substring) ‎ 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:1611:16, 15 February 2023 diff hist +223‎ N Record linking (Entity Resolution Entity Resolution) ‎ Created page with "== Time Complexity == $O(n^{2}k)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference ==" current
• 11:1611:16, 15 February 2023 diff hist +309‎ N Bellare Active Learning (Entity Resolution Entity Resolution) ‎ 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:1611:16, 15 February 2023 diff hist +426‎ N Ananthakrishna (Entity Resolution Entity Resolution) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +376‎ N EM Based Winkler (Entity Resolution Entity Resolution) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +333‎ N Ravikumar & Cohen Generative Models (Entity Resolution Entity Resolution) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +227‎ N Chen Ensembles of classifiers (Entity Resolution Entity Resolution) ‎ Created page with "== Time Complexity == $O(n^{2} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1989 == Reference =="
• 11:1611:16, 15 February 2023 diff hist +305‎ N Gupta & Sarawagi CRF (Entity Resolution Entity Resolution) ‎ 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:1611:16, 15 February 2023 diff hist +292‎ N Fellegi & Sunter Model (Entity Resolution Entity Resolution) ‎ 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:1611:16, 15 February 2023 diff hist +376‎ N McCreight (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +470‎ N Rytter (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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:1611:16, 15 February 2023 diff hist +360‎ N Farach (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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:1611:16, 15 February 2023 diff hist +415‎ N Süleyman Cenk Sahinalp ; Uzi Vishkin (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +384‎ N Hariharan (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +352‎ N Ukkonen and D. Wood (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +391‎ N Ukkonen (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +235‎ N Pratt (Constructing Suffix Trees Constructing Suffix Trees) ‎ Created page with "== Time Complexity == $O(n)$ == Space Complexity == words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == -" current
• 11:1611:16, 15 February 2023 diff hist +376‎ N Weiner's algorithm (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +396‎ N Ioannidou; Kyriaki; Mertzios; George B.; Nikolopoulos; Stavros D. (Longest Path on Interval Graphs Longest Path Problem) ‎ 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:1611:16, 15 February 2023 diff hist +339‎ N Naive (Constructing Suffix Trees Constructing Suffix Trees) ‎ 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 == -" current
• 11:1611:16, 15 February 2023 diff hist +370‎ N Patrick Posser (Stable Roommates Problem Stable Matching Problem) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +377‎ N S. S. TSENG and R. C. T. LEE (Stable Marriage Problem Stable Matching Problem) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +409‎ N Unsworth; C.; Prosser; P (Stable Marriage Problem Stable Matching Problem) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +372‎ N Gent; I.P.; Irving; R.W.; Manlove; D.F.; Prosser; P.; Smith; B.M. (Stable Marriage Problem Stable Matching Problem) ‎ 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" current
• 11:1611:16, 15 February 2023 diff hist +373‎ N Gaussian Elimination (Exact Laplacian Solver SDD Systems Solvers) ‎ 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 == -" current
• 11:1611:16, 15 February 2023 diff hist −365‎ Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) ‎No edit summary Tag: Manual revert
• 11:1611:16, 15 February 2023 diff hist +365‎ Chen; I. Kanj; and W. Jia. (The Vertex Cover Problem The Vertex Cover Problem) ‎No edit summary Tag: Reverted
• 11:1511:15, 15 February 2023 diff hist +315‎ N 9-point FFT (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +338‎ N 5-point cyclic reduction (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +338‎ N 9-point ADI iteration + smooth guess (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +315‎ N 5-point FFT (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +338‎ N 9-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +382‎ N 9-point Tensor product (2-Dimensional Poisson Problem Poisson Problem) ‎ 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" current
• 11:1511:15, 15 February 2023 diff hist +322‎ N 9-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) ‎ 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 ==" current
• 11:1511:15, 15 February 2023 diff hist +342‎ N 5-point ADI iteration (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +327‎ N 5-point SOR iteration (2-Dimensional Poisson Problem Poisson Problem) ‎ 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:1511:15, 15 February 2023 diff hist +338‎ N 5-point Gauss Seidel iteration (2-Dimensional Poisson Problem Poisson Problem) ‎ 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 =="