New pages
Jump to navigation
Jump to search
(newest | oldest) View (newer 50 | older 50) (20 | 50 | 100 | 250 | 500)
- 10:34, 15 February 2023 Horowitz and Sahni (Subset Sum The Subset-Sum Problem) (hist | edit) [352 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^{(n/{2})})$ == Space Complexity == $O({2}^{(n/{2})$}) (https://dl.acm.org/doi/10.1145/321812.321823) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference == https://dl.acm.org/doi/10.1145/321812.321823")
- 10:34, 15 February 2023 R-tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == R-Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(log n)$ (https://www.sciencedirect.com/science/article/pii/S1877050915019675, Table 2) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1984 == Reference == http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf")
- 10:34, 15 February 2023 K-d Tree (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [373 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == k-d Tree construction: $O(n log n)$ NNS: $O(n)$ == Space Complexity == $O(n)$ (https://dl.acm.org/doi/pdf/10.1145/355744.355745) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1975 == Reference == https://dl.acm.org/doi/pdf/10.1145/355744.355745")
- 10:34, 15 February 2023 Linear search (Nearest Neighbor Search (NNS) Nearest Neighbor Search) (hist | edit) [321 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: Only ever storing the current shortest distance and the corresponding node) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1940 == Reference == -")
- 10:34, 15 February 2023 Zhao-Saalfeld ( Line Simplification) (hist | edit) [371 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O(n)$ (Derived: There is an auxiliary sleeve set that is $O(n)$ size worst-case) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1997 == Reference == http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.494.7321")
- 10:34, 15 February 2023 Lang simplification ( Line Simplification) (hist | edit) [402 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from a point in the search interval to the search line, which is all $O(1)$ space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1969 == Reference == -")
- 10:34, 15 February 2023 Opheim simplification ( Line Simplification) (hist | edit) [477 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search ray and the current best, the distances from the next point to the ray and to the ray's origin, candidate point to stay in the simplified line) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1981 == Reference == http://dx.doi.org/10.2312/eg.19811012")
- 10:34, 15 February 2023 Reumann–Witkam ( Line Simplification) (hist | edit) [349 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ (Derived: The only auxiliary space used is the current search line and the distance from the next point to the line.) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1974 == Reference ==")
- 10:34, 15 February 2023 Visvalingam–Whyatt ( Line Simplification) (hist | edit) [333 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ (Derived: Storing each points effective area) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1993 == Reference == https://hull-repository.worktribe.com/output/459275")
- 10:33, 15 February 2023 Ramer–Douglas–Peucker algorithm ( Line Simplification) (hist | edit) [421 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$? (Derived: Recursive algorithm that has a worst-case recursion tree depth of O(n)?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/abs/pii/S0146664X72800170")
- 10:33, 15 February 2023 Long Multiplication ( Multiplication) (hist | edit) [289 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{2})$ == Space Complexity == $O(n)$ auxiliary bits (Easily derived (needed for intermediate results)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1940 == Reference ==")
- 10:33, 15 February 2023 Toom-3 ( Multiplication) (hist | edit) [433 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{4}6})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/3)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1969 == Reference == https://www.ams.org/journals/tran/1969-142-00/S0002-9947-1969-0249212-8/S0002-9947-1969-0249212-8.pdf")
- 10:33, 15 February 2023 Karatsuba Algorithm ( Multiplication) (hist | edit) [423 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{1.{5}8})$ == Space Complexity == $O(n)$ auxiliary bits (Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/2)+O(n))) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM? == Year == 1962 == Reference == http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng")
- 10:33, 15 February 2023 Rabin–Scott powerset construction ( NFA to DFA conversion) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O({2}^n)$ == Space Complexity == $O({1})$ (Derived: besides the O(2^n) output nodes and the O(n) input nodes, there's nothing to store) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1959 == Reference == https://ieeexplore.ieee.org/document/5392601")
- 10:33, 15 February 2023 Fast clipping (Rectangular Window Line Clipping) (hist | edit) [368 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1987 == Reference == https://www.sciencedirect.com/science/article/pii/0097849387900616")
- 10:33, 15 February 2023 Nicholl–Lee–Nicholl (Rectangular Window Line Clipping) (hist | edit) [344 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1987 == Reference == https://dl.acm.org/doi/10.1145/37401.37432")
- 10:33, 15 February 2023 Cyrus–Beck (Convex Polygonal Window; Convex Polyhedral window Line Clipping) (hist | edit) [370 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(np)$ == Space Complexity == $O({1})$ auxiliary? words (Easily derived? (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1978 == Reference == https://www.sciencedirect.com/science/article/pii/0097849378900213")
- 10:33, 15 February 2023 Liang–Barsky (Rectangular Window Line Clipping) (hist | edit) [346 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1984 == Reference == https://dl.acm.org/doi/10.1145/357332.357333")
- 10:33, 15 February 2023 Cohen–Sutherland (Rectangular Window Line Clipping) (hist | edit) [400 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n)$ == Space Complexity == $O({1})$ auxiliary words (Easily derived (O(1) per segment, space can be re-used)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word/Real RAM == Year == 1967 == Reference == https://books.google.com/books/about/Principles_of_interactive_computer_graph.html?id=inJ8AAAAIAAJ")
- 10:33, 15 February 2023 David Sankoff (Edit sequence, global alignment Sequence Alignment) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.ncbi.nlm.nih.gov/pmc/articles/PMC427531/")
- 10:33, 15 February 2023 Myers and Miller (Edit sequence, local alignment Sequence Alignment) (hist | edit) [392 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n+log(m)$) words (https://academic.oup.com/bioinformatics/article/4/1/11/205106?login=true) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1988 == Reference == https://academic.oup.com/bioinformatics/article/4/1/11/205106?login=true")
- 10:33, 15 February 2023 Altschul and Erickson (Edit sequence, local alignment Sequence Alignment) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1986 == Reference == https://link.springer.com/article/10.1007/BF02462326")
- 10:33, 15 February 2023 Gotoh (Edit sequence, local alignment Sequence Alignment) (hist | edit) [377 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses a constant number of m*n arrays, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1982 == Reference == https://www.sciencedirect.com/science/article/pii/0022283682903989")
- 10:33, 15 February 2023 FASTA (Edit sequence, local alignment Sequence Alignment) (hist | edit) [335 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1985 == Reference == https://www.ncbi.nlm.nih.gov/pubmed/2983426")
- 10:33, 15 February 2023 Hirschberg's algorithm (Edit sequence, constant-size alphabet Sequence Alignment) (hist | edit) [378 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/10.1145/360825.360861) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/Docs/Hirschberg-LCS-1975.pdf")
- 10:33, 15 February 2023 Masek; Patterson (Edit distance, constant-size alphabet Sequence Alignment) (hist | edit) [393 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn / log(n))$ == Space Complexity == $O(n)$ words (https://www.sciencedirect.com/science/article/pii/0022000080900021?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1980 == Reference == https://www.sciencedirect.com/science/article/pii/0022000080900021")
- 10:33, 15 February 2023 Smith–Waterman algorithm (Edit sequence, local alignment Sequence Alignment) (hist | edit) [362 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn^{2})$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1981 == Reference == https://www.sciencedirect.com/science/article/pii/0022283681900875")
- 10:33, 15 February 2023 Needleman–Wunsch algorithm (Edit sequence, global alignment Sequence Alignment) (hist | edit) [358 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O(mn)$ words (Uses an m*n array, whose contents are of size O(1)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://www.sciencedirect.com/science/article/pii/0022283670900574")
- 10:33, 15 February 2023 Rabin-Karp (RK) algorithm (Single String Search String Search) (hist | edit) [426 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn)$ == Space Complexity == $O({1})$ words (Derived: only storing a rolling hash) == Description == Hashing-based, compare the text and patterns via their hash functions == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://pdfs.semanticscholar.org/c47d/151f09c567013761632c89e237431c6291a2.pdf")
- 10:33, 15 February 2023 Boyer-Moore (BM) algorithm (Single String Search String Search) (hist | edit) [427 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(mn + s)$ == Space Complexity == $O(s)$ words (https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf) == Description == Heuristics-based, bad-character and good-suffix heuristics == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf")
- 10:33, 15 February 2023 Knuth-Morris-Pratt (KMP) algorithm (Single String Search String Search) (hist | edit) [413 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m+n)$ == Space Complexity == $O(m)$ words (https://www.semanticscholar.org/paper/Fast-Pattern-Matching-in-Strings-Knuth-Morris/5253fead88bfeaaa2930daccb7324a264cb681a9?p2df) == Description == Automaton-based == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1977 == Reference == https://pdfs.semanticscholar.org/4479/9559a1067e06b5a6bf052f8f10637707928f.pdf")
- 10:33, 15 February 2023 Naïve string-search algorithm (Single String Search String Search) (hist | edit) [295 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(m(n-m+{1}))$ == Space Complexity == $O({1})$ words (Derived (pointer algorithm)) == Description == Linear searching == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1940 == Reference == -")
- 10:33, 15 February 2023 Time-Bounded A* (TBA*) (Informed Search Informed Search) (hist | edit) [315 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2009 == Reference == https://www.cs.du.edu/~sturtevant/papers/TBA.pdf")
- 10:33, 15 February 2023 Anytime Repairing A* (ARA*) (Informed Search Informed Search) (hist | edit) [357 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2005 == Reference == https://papers.nips.cc/paper/2382-ara-anytime-a-with-provable-bounds-on-sub-optimality.pdf")
- 10:33, 15 February 2023 Theta* (Informed Search Informed Search) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2010 == Reference == http://idm-lab.org/bib/abstracts/papers/aaai07a.pdf")
- 10:33, 15 February 2023 Simplified Memory-Bounded A* (SMA*) (Informed Search Informed Search) (hist | edit) [332 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1992 == Reference == https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.7839")
- 10:33, 15 February 2023 Lifelong Planning A* (LPA*) (Informed Search Informed Search) (hist | edit) [318 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2001 == Reference == http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf")
- 10:33, 15 February 2023 Jump Point Search (JPS) (Informed Search Informed Search) (hist | edit) [345 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2011 == Reference == http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf")
- 10:33, 15 February 2023 Iterative Deepening A* (IDA*) (Informed Search Informed Search) (hist | edit) [328 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1985 == Reference == https://linkinghub.elsevier.com/retrieve/pii/0004370285900840")
- 10:32, 15 February 2023 Generalized Adaptive A* (GAA*) (Informed Search Informed Search) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == http://idm-lab.org/bib/abstracts/papers/aamas08b.pdf")
- 10:32, 15 February 2023 Fringe Saving A* (FSA*) (Informed Search Informed Search) (hist | edit) [319 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2008 == Reference == http://idm-lab.org/bib/abstracts/papers/aamas09d.pdf")
- 10:32, 15 February 2023 Bidirectional A* Algorithm (Informed Search Informed Search) (hist | edit) [388 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^{(d/{2})})$ == Space Complexity == $O(b^{(d/{2})$}) (Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 2007 == Reference == https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf")
- 10:32, 15 February 2023 A* Algorithm (Informed Search Informed Search) (hist | edit) [363 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(b^d)$ == Space Complexity == $O(b^d)$ (https://en.wikipedia.org/wiki/A*_search_algorithm: Stores all generated nodes in memory) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == == Year == 1968 == Reference == https://ieeexplore.ieee.org/document/4082128/")
- 10:32, 15 February 2023 Okunev; Johnson (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [314 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $O({1})$ words (Derived: all in-place calculations) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1997 == Reference == https://arxiv.org/abs/math/0506382")
- 10:32, 15 February 2023 Crout and LUP algorithms (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [355 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}({1})$ words (Derived: only storing 1 intermediate variable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2007 == Reference == https://en.wikipedia.org/wiki/Crout_matrix_decomposition")
- 10:32, 15 February 2023 Doolittle Algorithm (Square Matrix LU Decomposition LU Decomposition) (hist | edit) [296 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(n^{3})$ == Space Complexity == $\tilde{O}({1})$ words (Derived: only storing 1 intermediate variable) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1878 == Reference ==")
- 10:32, 15 February 2023 Naive Implementation (k-dimensional space, l m (or l infty) norm Closest Pair Problem) (hist | edit) [269 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(kn^{2})$ == Space Complexity == $O({1})$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1975 == Reference == -")
- 10:32, 15 February 2023 Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [337 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(min(V^{2}, ElogV)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == Yes, Las Vegas == Model of Computation == Word RAM == Year == 1995 == Reference == http://cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf")
- 10:32, 15 February 2023 Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [310 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Elog(V)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2006 == Reference == https://dl.acm.org/citation.cfm?id=2791187")
- 10:32, 15 February 2023 Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST)) (hist | edit) [320 bytes] Admin (talk | contribs) (Created page with "== Time Complexity == $O(Elog(V)$) == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1991 == Reference == https://link.springer.com/chapter/10.1007/BFb0028279")