New pages

Jump to navigation Jump to search
New pages
Hide registered users | Hide bots | Show redirects
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)
  • 10:36, 15 February 2023Terlaky's Criss-cross algorithm ( Linear Programming) (hist | edit) ‎[279 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m))$? (previously $O({2}^n)$) == Space Complexity == $O(nm)$ words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == -")
  • 10:36, 15 February 2023Simplex Algorithm ( Linear Programming) (hist | edit) ‎[279 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n*poly(n, m))$? (previously $O({2}^n)$) == Space Complexity == $O(nm)$ words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1947 == Reference == -")
  • 10:36, 15 February 2023Karmarkar's algorithm ( Linear Programming) (hist | edit) ‎[396 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3.5} L^{2} logL loglogL)$ == Space Complexity == $O(nmL)$ words (can be derived from paper?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1984 == Reference == https://web.archive.org/web/20131228145520/http://retis.sssup.it/~bini/teaching/optim2010/karmarkar.pdf")
  • 10:36, 15 February 2023Harrow (Quantum) (Sparse Linear System Linear System) (hist | edit) ‎[376 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(k^{2}*logn)$ == Space Complexity == $O(log n)$ qubits (https://arxiv.org/pdf/0811.3171.pdf) == Description == Quantum algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Quantum == Year == 2009 == Reference == https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.103.150502")
  • 10:36, 15 February 2023Conjugate Gradient (Approximation? with positive definite matrix Linear System) (hist | edit) ‎[379 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(m k^{0.5})$ == Space Complexity == $O(m)$ words (http://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1952 == Reference == https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf")
  • 10:36, 15 February 2023Byskov (4-Graph Coloring Graph Coloring) (hist | edit) ‎[404 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7504}^n)$ == Space Complexity == $O(n^{2})$? words (can be derived from algo 89 plus the paper's algo for finding MIS's?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0167637704000409?via%3Dihub")
  • 10:36, 15 February 2023Lawler (4-Graph Coloring Graph Coloring) (hist | edit) ‎[376 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O((m + n)*{2}^n)$ == Space Complexity == $O(n+m)$ words ((can be easily derived; see section 6 of ref)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
  • 10:36, 15 February 2023Beigel & Eppstein (3-Graph Coloring Graph Coloring) (hist | edit) ‎[388 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.3446}^n)$ == Space Complexity == $O(n^{2})$? words (can be derived from steps of algorithm? you add at most O(n^2) constraints, other info shouldn't take more than O(n^2) space, and you can reuse space during recursive steps) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1995 == Reference == https://ieeexplore.ieee.org/stamp/stamp.jsp?arnum...")
  • 10:36, 15 February 2023Schiermeyer (3-Graph Coloring Graph Coloring) (hist | edit) ‎[385 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.415}^n)$ == Space Complexity == $O(nm+n^{2})$ loose bound, possibly $O(n+m)$? words ((can be derived from steps of algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1994 == Reference == https://link.springer.com/chapter/10.1007/3-540-57899-4_51")
  • 10:36, 15 February 2023Lawler (3-Graph Coloring Graph Coloring) (hist | edit) ‎[397 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(m*n*{3}^{(n/{3})}) ~ O(mn({1.445})^n)$ == Space Complexity == $O(n+m)$ words ((can be easily derived; see section 6 of ref)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.sciencedirect.com/science/article/pii/002001907690065X?via%3Dihub")
  • 10:36, 15 February 2023James B Orlin's + KRT (King; Rao; Tarjan)'s algorithm (st-Maximum Flow Maximum Flow) (hist | edit) ‎[366 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Improvement of the KRT algorithm == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://dl.acm.org/citation.cfm?id=2488705")
  • 10:36, 15 February 2023Goldberg & Rao (Integer Maximum Flow Maximum Flow) (hist | edit) ‎[385 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(E^{1.5} Log(V^{2}/E) LogU)$ == Space Complexity == $O(V + E)$ words (Derived: creates and updates an auxiliary graph) == Description == Finding blocking flows == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://dl.acm.org/citation.cfm?id=290181")
  • 10:36, 15 February 2023Phillips & Westbrook (st-Maximum Flow Maximum Flow) (hist | edit) ‎[419 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE(Log(V;V/E)) + V^{2}(LogV)^{2} )$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1993 == Reference == https://dl.acm.org/citation.cfm?id=167201")
  • 10:36, 15 February 2023King et al. (KRT) (st-Maximum Flow Maximum Flow) (hist | edit) ‎[402 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{({2}+eps)})$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1992 == Reference == https://dl.acm.org/citation.cfm?id=139438")
  • 10:36, 15 February 2023Alon (st-Maximum Flow Maximum Flow) (hist | edit) ‎[430 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{({2.66})}LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1990 == Reference == https://www.sciencedirect.com/science/article/pii/002001909090024R")
  • 10:36, 15 February 2023Cheriyan et al. (st-Maximum Flow Maximum Flow) (hist | edit) ‎[448 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{3} / LogV)$ == Space Complexity == $O(V + E)$ words (Derived: essentially the same as (CH89) above but derandomized) == Description == Derandomization of Cheriyan & Hagerup == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Uniform-Cost RAM (is this the same as Word RAM?) == Year == 1990 == Reference == https://link.springer.com/chapter/10.1007/BFb0032035")
  • 10:36, 15 February 2023Cheriyan & Hagerup (st-Maximum Flow Maximum Flow) (hist | edit) ‎[436 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE*log(V))$ == Space Complexity == $O(V + E)$ words (Derived: d_heap and e_heap are size O(V). Adjacency list of a given vertex is O(V). Dynamic trees data structure is size O(E).) == Description == Push-relabel method == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1989 == Reference == https://ieeexplore.ieee.org/document/63465")
  • 10:36, 15 February 2023Ahuja & Orlin ( Maximum Flow) (hist | edit) ‎[382 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VE + V^{2}LogU)$ == Space Complexity == $O(ELogU)$ words (derived in sheet) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://www.researchgate.net/publication/38008130_A_Fast_and_Simple_Algorithm_for_the_Maximum_Flow_Problem")
  • 10:36, 15 February 2023Goldberg & Tarjan ( Maximum Flow) (hist | edit) ‎[413 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELog(V^{2}/E))$ == Space Complexity == $O(E)$ words (can be derived? also hints of space complexity might be in the paper) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20new%20approach.pdf")
  • 10:36, 15 February 2023Sleator & Tarjan ( Maximum Flow) (hist | edit) ‎[329 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELogV)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1983 == Reference == https://www.sciencedirect.com/science/article/pii/0022000083900065")
  • 10:35, 15 February 2023Cherkassky ( Maximum Flow) (hist | edit) ‎[366 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}E^{0.5})$ == Space Complexity == $O(E)$ words (https://core.ac.uk/download/pdf/81946904.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S037722179600269X")
  • 10:35, 15 February 2023Dinitz (with dynamic trees) ( Maximum Flow) (hist | edit) ‎[523 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(VELogU)$ == Space Complexity == $O(E)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1973 == Reference == https://www.scirp.org/(S(lz5mqp453edsnp55rrgjct55))/reference/ReferencesPapers.aspx?ReferenceID=1690549")
  • 10:35, 15 February 2023Dantzig ( Maximum Flow) (hist | edit) ‎[385 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(V^{2}EU)$ == Space Complexity == $O(VE)$? words (can be derived? (assuming this is referring to simplex algorithm)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1951 == Reference ==")
  • 10:35, 15 February 2023Mukhopadhyay (LCS Longest Common Subsequence) (hist | edit) ‎[389 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://www.sciencedirect.com/science/article/pii/0020025580900250) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0020025580900250")
  • 10:35, 15 February 2023Hunt and Szymanski (LCS Longest Common Subsequence) (hist | edit) ‎[381 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O((n + p) \log n)$ == Space Complexity == $O(p + n)$ words (https://cse.hkust.edu.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/HuSz77.pdf")
  • 10:35, 15 February 2023T. C. Hu ; M. T. Shing (Matrix Chain Ordering Problem Matrix Chain Multiplication) (hist | edit) ‎[293 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://citeseerx.ist.psu.edu/viewdoc/citations?doi=10.1.1.695.2923")
  • 10:35, 15 February 2023Hashing (kth Order Statistic kth Order Statistic) (hist | edit) ‎[267 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ words (Derived: size of hashtable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
  • 10:35, 15 February 2023Spreadsort (Non-Comparison Sorting Sorting) (hist | edit) ‎[400 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n*log n)$ == Space Complexity == $O(n)$? words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.semanticscholar.org/paper/The-Spreadsort-High-performance-General-case-Ross/41f5b49e9843b2d98b6b22a84924dae5761e6e52")
  • 10:35, 15 February 2023Burst Sort (Non-Comparison Sorting Sorting) (hist | edit) ‎[311 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(wn)$ == Space Complexity == $O(wn)$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://dl.acm.org/citation.cfm?doid=1005813.1041517")
  • 10:35, 15 February 2023Bead Sort (Non-Comparison Sorting Sorting) (hist | edit) ‎[386 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n^{2})$ words ((wikipedia page?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://web.archive.org/web/20170809110409/https://www.cs.auckland.ac.nz/~jaru003/research/publications/journals/beadsort.pdf")
  • 10:35, 15 February 2023Flash Sort (Non-Comparison Sorting Sorting) (hist | edit) ‎[353 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1998 == Reference == http://www.neubert.net/FSOIntro.html")
  • 10:35, 15 February 2023Naive sorting (Non-Comparison Sorting Sorting) (hist | edit) ‎[262 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
  • 10:35, 15 February 2023Thorup's Sorting Algorithm (Comparison Sorting Sorting) (hist | edit) ‎[386 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n loglogn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == https://www.sciencedirect.com/science/article/pii/S0196677402912113?via%3Dihub")
  • 10:35, 15 February 2023Bitonic Merge Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) ‎[433 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(log² n)$ == Space Complexity == $O({1})$? words (Paper claims "logspace uniform", so with O(log n) words, this is constant # of words) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == PRAC (shared-memory multiprocessor of the EREW PRAM variety) == Year == 1968 == Reference == https://epubs.siam.org/doi/abs/10.1137/0218014")
  • 10:35, 15 February 2023Shell Sort; (Sedgewick) (Comparison Sorting Sorting) (hist | edit) ‎[361 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{3}3})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0196677486900015?via%3Dihub")
  • 10:35, 15 February 2023Shell Sort; (Pratt) (Comparison Sorting Sorting) (hist | edit) ‎[327 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n log² n)$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://apps.dtic.mil/sti/pdfs/AD0740110.pdf")
  • 10:35, 15 February 2023Shell Sort; (Frank & Lazarus) (Comparison Sorting Sorting) (hist | edit) ‎[331 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.5})$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1960 == Reference == https://dl.acm.org/citation.cfm?doid=366947.366957")
  • 10:35, 15 February 2023Shell Sort; (Shell) (Comparison Sorting Sorting) (hist | edit) ‎[329 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O({1})$ (in-situ) words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1959 == Reference == https://dl.acm.org/citation.cfm?doid=368370.368387")
  • 10:35, 15 February 2023Cube Sort Parallel Implementation (Comparison Sorting Sorting) (hist | edit) ‎[349 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Parallel RAM == Year == 1992 == Reference == https://www.sciencedirect.com/science/article/pii/0196677492900166?via%3Dihub")
  • 10:35, 15 February 2023Tim Sort (Comparison Sorting Sorting) (hist | edit) ‎[269 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words ((can be easily derived)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2002 == Reference == -")
  • 10:35, 15 February 2023Quick Sort (Comparison Sorting Sorting) (hist | edit) ‎[365 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O( n² )$ == Space Complexity == $O(logn)$ words (https://academic.oup.com/comjnl/article/5/1/10/395338?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1961 == Reference == https://apps.dtic.mil/dtic/tr/fulltext/u2/740110.pdf")
  • 10:35, 15 February 2023Tree sort (Comparison Sorting Sorting) (hist | edit) ‎[396 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n logn)$ == Space Complexity == $O(n)$ words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1962 == Reference == http://www.neubert.net/FSOIntro.html")
  • 10:35, 15 February 2023Bitap algorithm (Single String Search String Search) (hist | edit) ‎[326 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(m)$ words (Derived: Uses a bit array of size $O(m)$) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1964 == Reference == https://en.wikipedia.org/wiki/Bitap_algorithm")
  • 10:35, 15 February 2023Bunch; Hopcroft (Square Matrix LU Decomposition LU Decomposition) (hist | edit) ‎[397 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2.{37}6})$ == Space Complexity == $\tilde{O}(n^{2})$ words (Derived: Uses Strassen multiplication and a constant number of $n \times n$ auxiliary matrices) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1974 == Reference == https://dl.acm.org/citation.cfm?id=248979")
  • 10:35, 15 February 2023Khuller; Matias Randomized Sieve ( Closest Pair Problem) (hist | edit) ‎[402 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$, not sure if this is auxiliary not mentioned (https://www.sciencedirect.com/science/article/pii/S0890540185710498, Theorem 2.3) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == not mentioned == Year == 1995 == Reference == https://dl.acm.org/citation.cfm?id=207181")
  • 10:35, 15 February 2023Fomin; Gaspers & Saurabh (4-Graph Coloring Graph Coloring) (hist | edit) ‎[654 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O({1.7272}^n)$ == Space Complexity == $O(n)$ words (Derived: we store the sets I and C (in algorithm enumIS), and the maximum size of these sets is equal to the number of vertices in the graph. The algorithm also stores the solution sets S1 and S2, which have a maximum size equal to the number of vertices in the graph. We also call a 3-coloring algorithm, which likely has O(n) space complexity) == Description == == Approximate? == Exac...")
  • 10:35, 15 February 2023Petford and Welsh (3-Graph Coloring Graph Coloring) (hist | edit) ‎[465 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (Derived: we store the coloring of each vertex in a dictionary and the maximum size of this dictionary is equal to the number of vertices in the graph, n.) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 1989 == Reference == https://www.sciencedirect.com/science/article/pii/0012365X89902148")
  • 10:35, 15 February 2023Rao-Blackwellized Particle Filtering SLAM (SLAM Algorithms SLAM Algorithms) (hist | edit) ‎[394 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? words? ((based on Section 4 of the paper?)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == https://papers.nips.cc/paper/1716-bayesian-map-learning-in-dynamic-environments.pdf")
  • 10:35, 15 February 2023Compressed Extended KF (SLAM Algorithms SLAM Algorithms) (hist | edit) ‎[421 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2002 == Reference == https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.999&rep=rep1&type=pdf")
  • 10:35, 15 February 2023UKF (SLAM Algorithms SLAM Algorithms) (hist | edit) ‎[401 bytes]Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O(n^{2})$? words? ((can be easily derived? it's mostly square matrices here)) == Description == == Approximate? == Approximate Approximation Factor: == Randomized? == No, deterministic == Model of Computation == == Year == 2000 == Reference == https://www.seas.harvard.edu/courses/cs281/papers/unscented.pdf")
(newest | oldest) View ( | ) (20 | 50 | 100 | 250 | 500)