New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 11:15, 15 February 2023 Todd–Coxeter algorithm (Bounded Subgroup Index Coset Enumeration) (hist | edit) [501 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(gkc)$ words (Defines O(k) tables, each with O(g) columns and O(c) rows) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1936 == Reference == https://www.cambridge.org/core/journals/proceedings-of-the-edinburgh-mathematical-society/article/practical-method-for-enumerating-cosets-of-a-finite-abstract-group/030657...")
- 11:15, 15 February 2023 Haselgrove; Leech and Trotter (Bounded Subgroup Index Coset Enumeration) (hist | edit) [387 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O(ng)$? words (Implementation stores a table whose number of required registers is the product of the number of generators (n) and the number of cosets (O(g))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 11:15, 15 February 2023 Muller's method (General Root Computation Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 3 estimates x_i, x_{i-1}, and x_{i-2}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1956 == Reference == https://www.jstor.org/stable/200...")
- 11:15, 15 February 2023 Ridder's method (General Root Computation Root Computation) (hist | edit) [478 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1979 == Reference == https://ieeexplore.ieee.org/document/1084580/")
- 11:15, 15 February 2023 Secant method (General Root Computation Root Computation) (hist | edit) [434 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store previous 2 estimates x_i and x_{i-1}; iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Newton's method (Root Computation with continuous first derivative Root Computation) (hist | edit) [479 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate $x_i$ and the derivative $f'$ (assuming this takes $O(1)$ space); iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Referenc...")
- 11:15, 15 February 2023 Halley's method (Root Computation with continuous second derivative Root Computation) (hist | edit) [482 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current estimate x_i and the derivatives f' and f'' (assuming this takes O(1) space); iterations take O(1) time and thus O(1) space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference...")
- 11:15, 15 February 2023 False position method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1690 == Reference == -")
- 11:15, 15 February 2023 Bisection method (General Root Computation Root Computation) (hist | edit) [425 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n_{max})$ == Space Complexity == $O({1})$ words (Store current endpoint values; iterations take $O(1)$ time and thus $O(1)$ space, and space can be re-used across iterations) == Description == == Approximate? == Approximate Approximation Factor: epsilon, additive == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1820 == Reference == -")
- 11:15, 15 February 2023 MRRR algorithm (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words (Need to compute and store some matrix of the form $(A-mu*I)^{(-1)}$ (for inverse iteration-like uses)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1999 == Reference == https://www.cs.utexas.edu/users/inderjit/public_papers/DesignMRRR_toms06.pdf")
- 11:15, 15 February 2023 Homotopy method (All eigenpairs; Eigenpair closest to mu; Any eigenpair; Any eigenvalue; All eigenvalues Eigenvalues (Iterative Methods)) (hist | edit) [403 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$?? words (Conservative bound on space used per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://www.scirp.org/(S(czeh2tfqyw2orz553k1w0r45))/reference/ReferencesPapers.aspx?ReferenceID=530065")
- 11:15, 15 February 2023 Folded spectrum method (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [438 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of O(n)-sized vectors per iteration; matrix-to-vector multiplication only requires O(n) aux space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1934 == Reference == https://journals.aps.org/pr/abstract/10.1103/PhysRev.46.828")
- 11:15, 15 February 2023 Divide-and-conquer (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [411 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n^{2})$ words (Stores reduction to tridiagonal form; recursion (S(n)=2S(n/2)+O(n^2)) should work out to O(n^2)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1986 == Reference == https://link.springer.com/content/pdf/10.1007/BF01389480.pdf")
- 11:15, 15 February 2023 Jacobi eigenvalue algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computes and stores results of GSG^T iterations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1846 == Reference == https://gdz.sub.uni-goettingen.de/id/PPN243919689_0030")
- 11:15, 15 February 2023 QR algorithm (All eigenvalues; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [361 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Computes and stores QR factorization at each iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1962 == Reference == https://academic.oup.com/comjnl/article/4/4/332/432033")
- 11:15, 15 February 2023 Laguerre iteration (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [266 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (^ see above) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Bisection method (Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [424 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$? words (Computing characteristic polynomial takes $O(n^2)$ space (via e.g. Faddeev–LeVerrier algorithm); rest of algo can be done in $O(n)$ space (related to root computation)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1985 == Reference == -")
- 11:15, 15 February 2023 LOBPCG algorithm (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words (Requires only a constant number of $O(n)$-sized vectors per iteration) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1948 == Reference == -")
- 11:15, 15 February 2023 Rayleigh quotient iteration (Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [299 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu_i*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Inverse iteration (Eigenpair closest to mu; Any eigenpair; Any eigenvalue Eigenvalues (Iterative Methods)) (hist | edit) [360 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ words (Need to compute and store $(A-mu*I)^{(-1)}$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1921 == Reference == https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19210010104")
- 11:15, 15 February 2023 Weiler–Atherton clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [382 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1977 == Reference == https://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf")
- 11:15, 15 February 2023 Vatti clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/129902.129906")
- 11:15, 15 February 2023 Sutherland–Hodgman algorithm (Polygon Clipping with Convex Clipping Polygon Polygon Clipping) (hist | edit) [464 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary words (Each iteration, keeps track of updated polygon after clipping by a side. Note that there can be at most $O(n)$ intersection points due to the clipping polygon being convex) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/360767.360802")
- 11:15, 15 February 2023 Gupta-Sproull algorithm (Line Drawing Line Drawing) (hist | edit) [459 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1981 == Reference == http://www.cs.gettysburg.edu/~ilinkin/courses/Fall-2014/cs373/handouts/papers/gs-fegsd-81.pdf")
- 11:15, 15 February 2023 Greiner–Hormann clipping algorithm (Polygon Clipping with Arbitrary Clipping Polygon Polygon Clipping) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ ? == Space Complexity == $O(n^{2})$ auxiliary? words (Needs to keep track of (possibly) $O(n^2)$ intersection points) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1998 == Reference == http://davis.wpi.edu/~matt/courses/clipping/")
- 11:15, 15 February 2023 Bresenham's line algorithm (Line Drawing Line Drawing) (hist | edit) [442 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1965 == Reference == https://web.archive.org/web/20080528040104/http://www.research.ibm.com/journal/sj/041/ibmsjIVRIC.pdf")
- 11:15, 15 February 2023 Xiaolin Wu's line algorithm (Line Drawing Line Drawing) (hist | edit) [423 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade and what shading to use) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1991 == Reference == http://www-users.mat.umk.pl/~gruby/teaching/lgim/1_wu.pdf")
- 11:15, 15 February 2023 Digital Differential Analyzer (Line Drawing Line Drawing) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Gao’s additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn loglogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2010 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5625613")
- 11:15, 15 February 2023 Naive algorithm (Line Drawing Line Drawing) (hist | edit) [343 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words? (Constant number of O(1)-word-sized variables (for determining which pixels to shade) is sufficient) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference == -")
- 11:15, 15 February 2023 Wang-Zhu-Cantor additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [383 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n(logn)$^{1.{58}5}) == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1988 == Reference == https://ieeexplore.ieee.org/document/1926/")
- 11:15, 15 February 2023 Von zur Gathen-Gerhard additive FFT (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n (logn)$^{2}) == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/236869.236882) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1996 == Reference == https://dl.acm.org/doi/10.1145/236869.236882")
- 11:15, 15 February 2023 Radix sorting method (General Permutations Generating Random Permutations) (hist | edit) [309 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Need to keep track of randomly generated numbers, but otherwise see radix sort) == Description == == Approximate? == Exact == Randomized? == Yes, ?? == Model of Computation == Word RAM == Year == 1887 == Reference == -")
- 11:15, 15 February 2023 Bergland; Glenn radix-8 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [340 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (https://ieeexplore.ieee.org/document/1162043) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1969 == Reference == https://ieeexplore.ieee.org/document/1162043")
- 11:15, 15 February 2023 Extended Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [351 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 2001 == Reference == https://ieeexplore.ieee.org/document/917698")
- 11:15, 15 February 2023 Gentleman; Morven and Gordon Sande radix-4 algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [359 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1966 == Reference == http://cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf")
- 11:15, 15 February 2023 Yavne Split Radix FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [350 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1968 == Reference == https://dl.acm.org/citation.cfm?id=1476610")
- 11:15, 15 February 2023 Bruun's FFT algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [375 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes O(n) remainders per stage; storage space can be reused across stages) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://ieeexplore.ieee.org/document/1163036/")
- 11:15, 15 February 2023 Rader–Brenner algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1976 == Reference == https://ieeexplore.ieee.org/document/1162805")
- 11:15, 15 February 2023 Naive algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O({1})$ words (Derived: You only need a constant number of variables that are of $O(1)$ size at any given time) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == -")
- 11:15, 15 February 2023 Cooley–Tukey algorithm (Discrete Fourier Transform Discrete Fourier Transform) (hist | edit) [409 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$? words (Computes and keeps track of DFTs for recursive subcases) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1965 == Reference == https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf")
- 11:15, 15 February 2023 Fleury's algorithm + Thorup (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [408 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E log^{3}(E)$ loglogE) == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf")
- 11:15, 15 February 2023 Hierholzer's algorithm (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [308 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E)$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1873 == Reference == -")
- 11:15, 15 February 2023 Fleury's algorithm + Tarjan (Constructing Eulerian Trails in a Graph Constructing Eulerian Trails in a Graph) (hist | edit) [401 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{2})$ == Space Complexity == $O(E)$ words (Keep track of current path + remaining edges needed to be traversed) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://collaborate.princeton.edu/en/publications/a-note-on-finding-the-bridges-of-a-graph")
- 11:15, 15 February 2023 Mucha and Sankowski ( Maximum-Weight Matching) (hist | edit) [268 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2004 == Reference == https://dl.acm.org/doi/10.1109/FOCS.2004.40")
- 11:15, 15 February 2023 Micali; Vazirani ( Maximum-Weight Matching) (hist | edit) [276 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3} logn)$ == Space Complexity == () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1980 == Reference == https://ieeexplore.ieee.org/document/4567800")
- 11:15, 15 February 2023 Edmonds (Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [418 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn^{2})$?? words (At worst, keeps track of the entire sequence of graphs created; it's possible this can be improved?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1965 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/69B/jresv69Bn1-2p125_A1b.pdf")
- 11:15, 15 February 2023 Lipton; Mehta (2-player Nash Equilibria) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{(O(log n)$)} (previously $O(n^{2} logn)$????) == Space Complexity == (see sheet {2}) words () == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://dl.acm.org/doi/10.1145/779928.779933")
- 11:15, 15 February 2023 Hungarian algorithm (Bipartite Maximum-Weight Matching Maximum-Weight Matching) (hist | edit) [464 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{4})$ == Space Complexity == $O(n^{2})$ words (Either graph interpretation maintains O(n^2) orientations and O(n) potential or matrix interpretation manipulates an O(n)*O(n) auxiliary matrix) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1955 == Reference == https://web.eecs.umich.edu/~pettie/matching/Kuhn-hungarian-assignment.pdf")
- 11:15, 15 February 2023 Lemke–Howson algorithm (2-player Nash Equilibria) (hist | edit) [347 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == {2}^{($O(n+m)$)} (previously $O(n^{4})$????) == Space Complexity == $O(mn)$? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://epubs.siam.org/doi/abs/10.1137/0112033?journalCode=smjmap.1")