User contributions for Admin
Jump to navigation
Jump to search
15 February 2023
- 10:3710:37, 15 February 2023 diff hist +316 N Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(E*\alpha(E, V))$ == Space Complexity == $O(E)$ auxiliary?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf"
- 10:3710:37, 15 February 2023 diff hist +423 N Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(Elog(V))$ == Space Complexity == $O(E)$ auxiliary? words (Kruskal-based, with minimal overhead? filtering should only remove edges, and each edge should only require O(1) information) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://dl.acm.org/citation.cfm?id=2791225"
- 10:3710:37, 15 February 2023 diff hist +359 N Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(EloglogV)$ == Space Complexity == $O(E)$ auxiliary? words (keep track of copy of graph where edges may be deleted?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://epubs.siam.org/doi/abs/10.1137/0205051"
- 10:3710:37, 15 February 2023 diff hist +345 N Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(EloglogV)$ == Space Complexity == $O(E)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1975 == Reference == https://www.sciencedirect.com/science/article/pii/0020019075900563"
- 10:3710:37, 15 February 2023 diff hist +311 N Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(ElogE)$ == Space Complexity == $O(E)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www.jstor.org/stable/2033241"
- 10:3710:37, 15 February 2023 diff hist +320 N Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(E + VlogV)$ == Space Complexity == $O(V)$ auxiliary? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1987 == Reference == https://dl.acm.org/citation.cfm?id=28874"
- 10:3710:37, 15 February 2023 diff hist +319 N Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1957 == Reference == https://ieeexplore.ieee.org/document/6773228" current
- 10:3710:37, 15 February 2023 diff hist +276 N Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST)) Created page with "== Time Complexity == $O(ElogV)$ == Space Complexity == $O(V)$ auxiliary words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1926 == Reference == -"
- 10:3710:37, 15 February 2023 diff hist +335 N Hong’s algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V(V+E))$ == Space Complexity == $O(V+E)$? words (Building recursive subgraphs) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2013 == Reference == https://stanford-ppl.github.io/website/papers/sc13-hong.pdf" current
- 10:3710:37, 15 February 2023 diff hist +423 N CH Algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(VE)$ == Space Complexity == $O(V+E)$? words (Each vertex needs to keep track of one color; then we need to build recursive subgraphs) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2004 == Reference == https://research.vu.nl/en/publications/on-distributed-verification-and-verified-distribution" current
- 10:3710:37, 15 February 2023 diff hist +364 N OBF Algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V(V+E))$ == Space Complexity == $O(E+V^{2})$ total words (https://ris.utwente.nl/ws/files/6872352/Barnat09distributed.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2011 == Reference == https://ieeexplore.ieee.org/document/8133154" current
- 10:3710:37, 15 February 2023 diff hist +337 N Munro’s algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(E + VlogV)$ == Space Complexity == $O(V)$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1971 == Reference == https://www.sciencedirect.com/science/article/pii/0020019071900068"
- 10:3710:37, 15 February 2023 diff hist +323 N Couvreur (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1999 == Reference == https://link.springer.com/chapter/10.1007/3-540-48119-2_16" current
- 10:3710:37, 15 February 2023 diff hist +359 N Renault’s Algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(p*(V+E)*\alpha(V, E))$ == Space Complexity == $O(V)$ per processor words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2009 == Reference == https://link.springer.com/chapter/10.1007/978-3-642-45221-5_44" current
- 10:3710:37, 15 February 2023 diff hist +339 N Lowe’s Algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V^{2})$ == Space Complexity == $O(V)$ per processor words ((can be easily derived?)) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2014 == Reference == http://www.cs.ox.ac.uk/people/gavin.lowe/parallelDFS.html" current
- 10:3710:37, 15 February 2023 diff hist +365 N Paul Purdom (Transitive Closure Strongly Connected Components) Created page with "== Time Complexity == $O(V^{2}+VE)$ == Space Complexity == $O(V^{2})$ words (https://link.springer.com/content/pdf/10.1007/BF01940892.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1970 == Reference == https://link.springer.com/article/10.1007%2FBF01940892" current
- 10:3710:37, 15 February 2023 diff hist +425 N Path-based depth-first search Gabow (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V+E)$ total, $O(V)$ auxiliary? words (https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2000 == Reference == https://www.sciencedirect.com/science/article/pii/S002001900000051X?via%3Dihub" current
- 10:3710:37, 15 February 2023 diff hist +376 N Pearce (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (https://www.sciencedirect.com/science/article/pii/S0020019015001532) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2016 == Reference == https://www.sciencedirect.com/science/article/pii/S0020019015001532" current
- 10:3710:37, 15 February 2023 diff hist +376 N Fleischer forward-backward (FB) algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(ElogV+V)$ == Space Complexity == $O(V+E)$ words (constructing recursive subgraphs? and reuse space across recursive calls) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2003 == Reference == https://ldhulipala.github.io/readings/sequential-scc.pdf"
- 10:3710:37, 15 February 2023 diff hist +347 N Path-based strong components algorithm; Dijkstra (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (constant number of auxiliary stacks?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1976 == Reference == https://www.worldcat.org/title/discipline-of-programming/oclc/1958445" current
- 10:3710:37, 15 February 2023 diff hist +441 N Tarjan's strongly connected components algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V)$ words (https://www.sciencedirect.com/science/article/pii/S0020019015001532) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1972 == Reference == https://www.semanticscholar.org/paper/Depth-First-Search-and-Linear-Graph-Algorithms-Tarjan/385742fffcf113656f0d3cf6c06ef95cb8439dc6" current
- 10:3610:36, 15 February 2023 diff hist +367 N Kosaraju's algorithm (SCCs Strongly Connected Components) Created page with "== Time Complexity == $O(V+E)$ == Space Complexity == $O(V+E)$ words (auxiliary data structures take up at most that much space) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1978 == Reference == https://www.sciencedirect.com/science/article/pii/0898122181900080" current
- 10:3610:36, 15 February 2023 diff hist +368 N Miller; Stout (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(logn)$ time using $O(n)$ processors == Space Complexity == $O(n)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == EREW PRAM, possibly others (see paper) == Year == 1988 == Reference == https://cse.buffalo.edu/faculty/miller/Papers/IEEETC88a.pdf"
- 10:3610:36, 15 February 2023 diff hist +350 N Chan's algorithm (2-dimensional; 3-dimensional Convex Hull) Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://link.springer.com/article/10.1007/BF02712873) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1996 == Reference == https://link.springer.com/article/10.1007/BF02712873" current
- 10:3610:36, 15 February 2023 diff hist +336 N The ultimate planar convex hull algorithm (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(n log h)$ == Space Complexity == $O(n)$ words (https://ecommons.cornell.edu/handle/1813/6417) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://ecommons.cornell.edu/handle/1813/6417" current
- 10:3610:36, 15 February 2023 diff hist +331 N Andrew's algorithm (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1979 == Reference == https://www.sciencedirect.com/science/article/pii/0020019079900723" current
- 10:3610:36, 15 February 2023 diff hist +287 N Preparata and Hong (2-dimensional; 3-dimensional Convex Hull) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=359430"
- 10:3610:36, 15 February 2023 diff hist +304 N W. Eddy Quickhull (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(nh)$ == Space Complexity == $O(h)$? words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1977 == Reference == https://dl.acm.org/citation.cfm?id=355766" current
- 10:3610:36, 15 February 2023 diff hist +342 N Graham (2-dimensional Convex Hull) Created page with "== Time Complexity == $O(nlogn)$ == Space Complexity == $O(n)$ words (can be easily derived) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1972 == Reference == https://www.sciencedirect.com/science/article/pii/0020019072900452?via%3Dihub"
- 10:3610:36, 15 February 2023 diff hist +299 N Goodrich (Reporting all intersection points, line segments Line segment intersection) Created page with "== Time Complexity == $O(log^{2}(n))$ == Space Complexity == $O(n+k)$ total? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == CREW PRAM == Year == 1989 == Reference == https://dl.acm.org/citation.cfm?id=72950"
- 10:3610:36, 15 February 2023 diff hist +397 N Boissonnat; Snoeyink (Reporting all intersection points, generalized segments Line segment intersection) Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://dl.acm.org/citation.cfm?id=304991) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM, under more restrictions/considerations? (predicate arithmetic) == Year == 1999 == Reference == https://dl.acm.org/citation.cfm?id=304991"
- 10:3610:36, 15 February 2023 diff hist +347 N Balaban. (Reporting all intersection points, generalized segments Line segment intersection) Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://dl.acm.org/doi/pdf/10.1145/220279.220302) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1995 == Reference == https://dl.acm.org/doi/pdf/10.1145/220279.220302"
- 10:3610:36, 15 February 2023 diff hist +452 N Jean-Daniel Boissonnat and Franco P. Preparata. (Reporting all intersection points, generalized segments Line segment intersection) Created page with "== Time Complexity == $O( n log n + k log n)$ == Space Complexity == $O(n)$ words (https://epubs.siam.org/doi/epdf/10.1137/S0097539797329373) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM, under more restrictions/considerations? (predicate arithmetic, exact arithmetic) == Year == 1997 == Reference == https://epubs.siam.org/doi/abs/10.1137/S0097539797329373"
- 10:3610:36, 15 February 2023 diff hist +388 N NIEVERGELT. J.. AND PREPARATA (Section 3) (Reporting all intersection points, convex polygons Line segment intersection) Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n)$ words (https://courses.cs.duke.edu/cps234/spring04/papers/NP82.pdf) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1982 == Reference == https://pdfs.semanticscholar.org/a571/cc92218132a1b0e65c2adbf663c79d015737.pdf"
- 10:3610:36, 15 February 2023 diff hist +442 N CHAZELLE (Reporting all intersection points, line segments Line segment intersection) Created page with "== Time Complexity == $O( n*log^{2}(n)/(log log n) + k)$ == Space Complexity == $O(n+k)$ total (and possibly auxiliary as well?) words (https://www.sciencedirect.com/science/article/pii/0022000086900255) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1986 == Reference == https://www.sciencedirect.com/science/article/pii/0022000086900255" current
- 10:3610:36, 15 February 2023 diff hist +348 N Chazelle & Edelsbrunner (Reporting all intersection points, line segments Line segment intersection) Created page with "== Time Complexity == $O( nlog n + k )$ == Space Complexity == $O(n+k)$ total? words (https://dl.acm.org/doi/10.1145/147508.147511) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Real RAM == Year == 1992 == Reference == https://dl.acm.org/doi/10.1145/147508.147511"
- 10:3610:36, 15 February 2023 diff hist +304 N Lee and Sidford ( Linear Programming) Created page with "== Time Complexity == $O((nnz(A) + n^{2}) n^{0.5})$ == Space Complexity == $O(nm+n^{2})$?? words () == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2015 == Reference == https://arxiv.org/abs/1503.01752"
- 10:3610:36, 15 February 2023 diff hist +497 N Cohen; Lee and Song ( Linear Programming) Created page with "== Time Complexity == $O(n^{max(omega, {2.5}-alpha/{2}, {13}/{6})}*polylog(n, m, L))$, where omega is the exponent on matrix multiplication, alpha is the dual exponent of matrix multiplication; currently $O(n^{2.37285956})$ == Space Complexity == $O(nm+n^{2})$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 2018 == Reference == https://ar..."
- 10:3610:36, 15 February 2023 diff hist +312 N Affine scaling ( Linear Programming) Created page with "== Time Complexity == ? (originally $O(n^{3.5} L)$ but seems unclear) == Space Complexity == $O(nm+m^{2})$? words (can be easily derived?) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1967 == Reference == -" current
- 10:3610:36, 15 February 2023 diff hist +304 N Terlaky's Criss-cross algorithm ( Linear Programming) 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:3610:36, 15 February 2023 diff hist +304 N Simplex Algorithm ( Linear Programming) 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:3610:36, 15 February 2023 diff hist +396 N Karmarkar's algorithm ( Linear Programming) 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" current
- 10:3610:36, 15 February 2023 diff hist +373 N Harrow (Quantum) (Sparse Linear System Linear System) 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:3610:36, 15 February 2023 diff hist +379 N Conjugate Gradient (Approximation? with positive definite matrix Linear System) 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" current
- 10:3610:36, 15 February 2023 diff hist +404 N Byskov (4-Graph Coloring Graph Coloring) 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" current
- 10:3610:36, 15 February 2023 diff hist +376 N Lawler (4-Graph Coloring Graph Coloring) 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" current
- 10:3610:36, 15 February 2023 diff hist −97 Beigel & Eppstein (3-Graph Coloring Graph Coloring) No edit summary
- 10:3610:36, 15 February 2023 diff hist +485 N Beigel & Eppstein (3-Graph Coloring Graph Coloring) 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:3610:36, 15 February 2023 diff hist +385 N Schiermeyer (3-Graph Coloring Graph Coloring) 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" current
- 10:3610:36, 15 February 2023 diff hist +399 N Lawler (3-Graph Coloring Graph Coloring) 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"