New pages

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

• 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")
• 11:15, 15 February 2023 ‎Segundo; Artieda; Strash Parallel (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[473 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ total work? (previously this cell said $O(n^{4})$) == Space Complexity == $O(n^{2})$ auxiliary?? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements? (this algo builds off of Bron-Kerbosch)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://arxiv.org/pdf/1801.00202.pdf")
• 11:15, 15 February 2023 ‎Tomita; Tanaka & Takahashi (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[374 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf")
• 11:15, 15 February 2023 ‎Akkoyunlu; E. A. (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[390 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})$}) == Space Complexity == $O(n^{2})$ auxiliary?? words (See Bron-Kerbosch (seems like a similar approach?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == http://www.dcs.gla.ac.uk/~pat/jchoco/clique/enumeration/papers/SMJ000001%5B1%5D.pdf")
• 11:15, 15 February 2023 ‎Bron–Kerbosch algorithm (Enumerating Maximal Cliques, arbitrary graph Clique Problems) (hist | edit) ‎[379 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O({3}^{(n/{3})})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Keep track of an O(n)-sized recursive stack with O(n)-sized lists as elements?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://dl.acm.org/doi/10.1145/362342.362367")
• 11:15, 15 February 2023 ‎Finch (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[531 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2} E)$ == Space Complexity == $O(V^{2})$? words (Seems to store/update a constant number of values per pair of nodes (one from each graph)) == Description == energy-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == https://direct.mit.edu/neco/article-pdf/10/7/1873/813998/089976698300017188.pdf?casa_token=nCYv9xO_Cc4AAAAA:EHiG4v8QmQju6u9...")
• 11:15, 15 February 2023 ‎Tao D; Tang X; Li X et al ( Graph Edit Distance Computation) (hist | edit) ‎[281 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == () == Description == EDH == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2006 == Reference == https://eprints.bbk.ac.uk/id/eprint/443/1/Binder1.pdf")
• 11:15, 15 February 2023 ‎Wang Y-K; Fan K-C; Horng J-T ( Graph Edit Distance Computation) (hist | edit) ‎[288 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} loglogE)$ == Space Complexity == () == Description == Genetics-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == https://doi.org/10.1109/3477.604100")
• 11:15, 15 February 2023 ‎Neuhaus, Riesen, Bunke (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[363 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(wV)$ words (Derived: number of nodes under consideration at once) == Description == A*-Beamsearch == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://link.springer.com/chapter/10.1007/11815921_17")
• 11:15, 15 February 2023 ‎Alberto Sanfeliu and King-Sun Fu ( Graph Edit Distance Computation) (hist | edit) ‎[272 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} E^{2})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1983 == Reference == https://doi.org/10.1109/TSMC.1983.6313167")
• 11:15, 15 February 2023 ‎K Riesen (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[337 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ words (Space complexity of A*) == Description == A* with bipartite heuristic == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://doi.org/10.1007/978-3-642-38221-5_15")
• 11:15, 15 February 2023 ‎L Chang (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[400 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V E^{2} logV)$ == Space Complexity == $O(V)$ words (Theorem 5.1, and the bound on T_{\leq \delta ...} is V\log V https://doi.org/10.48550/arXiv.1709.06810) == Description == AStar+ == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2017 == Reference == https://doi.org/10.48550/arXiv.1709.06810")
• 11:15, 15 February 2023 ‎Y Bai (Inexact GED Graph Edit Distance Computation) (hist | edit) ‎[417 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V^{2})$ words (Derived: Auxiliary matrices for the neural network of size VxV) == Description == SimGNN == Approximate? == Approximate Approximation Factor: none stated == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://asset-pdf.scinapse.io/prod/2886034153/2886034153.pdf")
• 11:15, 15 February 2023 ‎X Chen (Exact GED Graph Edit Distance Computation) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(VS)$ == Space Complexity == $O(wV^{2})$ words (Theorem 5, https://doi.org/10.1016/j.knosys.2018.10.002) == Description == Beam Stack Search == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2019 == Reference == https://doi.org/10.1016/j.knosys.2018.10.002")
• 11:15, 15 February 2023 ‎Stephen Alstrup, Cyril Gavoille, Haim Kaplan & Theis Rauhe (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[362 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words ((see original reference, noting that a word is O(log n) bits)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://link.springer.com/article/10.1007/s00224-004-1155-5")
• 11:15, 15 February 2023 ‎Berkman; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[333 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ ? == Space Complexity == $O(n)$ words (space bounded by pre-processing time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/a227803.pdf")
• 11:15, 15 February 2023 ‎Schieber; Vishkin (Lowest Common Ancestor with Static Trees Lowest Common Ancestor) (hist | edit) ‎[372 bytes] ‎Admin (talk | contribs) (Created page with "== Time Complexity == $O(n+m)$ == Space Complexity == $O(n)$ words (https://www.proquest.com/docview/919780720?pq-origsite=gscholar&fromopenview=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://epubs.siam.org/doi/abs/10.1137/0217079?journalCode=smjcat")

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