Undirected, General MST: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
V: number of vertices | $V$: number of vertices | ||
E: number of edges | $E$: number of edges | ||
U: maximum edge weight | $U$: maximum edge weight | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 26: | Line 26: | ||
|- | |- | ||
| [[Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal’s algorithm with demand-sorting]] || 1991 || $O( | | [[Kruskal’s algorithm with demand-sorting (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal’s algorithm with demand-sorting]] || 1991 || $O(E \log V)$ || $O(E)$ || Exact || Deterministic || [https://link.springer.com/chapter/10.1007/BFb0028279 Time] | ||
|- | |- | ||
| [[Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Quick Kruskal algorithm]] || 2006 || $O( | | [[Quick Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Quick Kruskal algorithm]] || 2006 || $O(E \log V)$ || $O(E)$ || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=2791187 Time] | ||
|- | |- | ||
| [[Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Karger; Klein & Tarjan]] || 1995 || $O(min(V^{2}, ElogV)$) || $O(E)$ | | [[Karger; Klein & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Karger; Klein & Tarjan]] || 1995 || $O(min(V^{2}, ElogV)$) || $O(E)$ || Exact || Randomized || [http://cs.brown.edu/research/pubs/pdfs/1995/Karger-1995-RLT.pdf Time] | ||
|- | |- | ||
| [[Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Borůvka's algorithm]] || 1926 || $O( | | [[Borůvka's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Borůvka's algorithm]] || 1926 || $O(E \log V)$ || $O(V)$ auxiliary || Exact || Deterministic || | ||
|- | |- | ||
| [[Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + adjacency matrix searching]] || 1957 || $O(V^{2})$ || $O(V)$ auxiliary || Exact || Deterministic || [https://ieeexplore.ieee.org/document/6773228 Time] | | [[Prim's algorithm + adjacency matrix searching (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + adjacency matrix searching]] || 1957 || $O(V^{2})$ || $O(V)$ auxiliary || Exact || Deterministic || [https://ieeexplore.ieee.org/document/6773228 Time] | ||
|- | |- | ||
| [[Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + Fibonacci heaps; Fredman & Tarjan]] || 1987 || $O(E + | | [[Prim's algorithm + Fibonacci heaps; Fredman & Tarjan (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + Fibonacci heaps; Fredman & Tarjan]] || 1987 || $O(E + V \log V)$ || $O(V)$ auxiliary? || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=28874 Time] | ||
|- | |- | ||
| [[Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal's algorithm]] || 1956 || $O( | | [[Kruskal's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Kruskal's algorithm]] || 1956 || $O(E \log E)$ || $O(E)$ auxiliary || Exact || Deterministic || [https://www.jstor.org/stable/2033241 Time] | ||
|- | |- | ||
| [[Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Yao's algorithm]] || 1975 || $O( | | [[Yao's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Yao's algorithm]] || 1975 || $O(E \log \log V)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://www.sciencedirect.com/science/article/pii/0020019075900563 Time] | ||
|- | |- | ||
| [[Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Cheriton-Tarjan Algorithm]] || 1976 || $O( | | [[Cheriton-Tarjan Algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Cheriton-Tarjan Algorithm]] || 1976 || $O(E \log \log V)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://epubs.siam.org/doi/abs/10.1137/0205051 Time] | ||
|- | |- | ||
| [[Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Filter Kruskal algorithm]] || 2009 || $O( | | [[Filter Kruskal algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Filter Kruskal algorithm]] || 2009 || $O(E \log V)$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://dl.acm.org/citation.cfm?id=2791225 Time] | ||
|- | |- | ||
| [[Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Chazelle's algorithm]] || 2000 || $O(E*\alpha(E, V))$ || $O(E)$ auxiliary?? || Exact || Deterministic || [https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf Time] | | [[Chazelle's algorithm (Undirected, General MST Minimum Spanning Tree (MST))|Chazelle's algorithm]] || 2000 || $O(E*\alpha(E, V))$ || $O(E)$ auxiliary?? || Exact || Deterministic || [https://www.cs.princeton.edu/~chazelle/pubs/mst.pdf Time] | ||
|- | |- | ||
| [[Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST))|Thorup (reverse-delete)]] || 2000 || $O(E | | [[Thorup (reverse-delete) (Undirected, General MST Minimum Spanning Tree (MST))|Thorup (reverse-delete)]] || 2000 || $O(E \log V (\log \log V)^{3})$ || $O(E)$ auxiliary? || Exact || Deterministic || [https://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf Time] | ||
|- | |- | ||
| [[Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST))|Bader & Cong Parallel Implementation ]] || 2006 || $O(E log(V)$/p) || $O(V)$ total || Exact || Parallel || [https://www.sciencedirect.com/science/article/pii/S0743731506001262 Time] | | [[Bader & Cong Parallel Implementation (Undirected, General MST Minimum Spanning Tree (MST))|Bader & Cong Parallel Implementation ]] || 2006 || $O(E \log(V)$/p) || $O(V)$ total || Exact || Parallel || [https://www.sciencedirect.com/science/article/pii/S0743731506001262 Time] | ||
|- | |- | ||
| [[Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + binary heap]] || - || $O(ElogV)$ || $O(V)$ auxiliary? || Exact || Deterministic || | | [[Prim's algorithm + binary heap (Undirected, General MST Minimum Spanning Tree (MST))|Prim's algorithm + binary heap]] || - || $O(ElogV)$ || $O(V)$ auxiliary? || Exact || Deterministic || | ||
| Line 65: | Line 65: | ||
[[File:Minimum Spanning Tree (MST) - Undirected, General MST - Time.png|1000px]] | [[File:Minimum Spanning Tree (MST) - Undirected, General MST - Time.png|1000px]] | ||
== References/Citation == | == References/Citation == | ||
Latest revision as of 09:06, 28 April 2023
Description
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected; edge-weighted undirected graph that connects all the vertices together; without any cycles and with the minimum possible total edge weight. Here, there are no restrictions on edge weights or graph density.
Related Problems
Subproblem: Undirected, Dense MST, Undirected, Planar MST, Undirected, Integer Weights MST
Related: Undirected, Planar MST, Undirected, Integer Weights MST, Directed (Optimum Branchings), General MST, Directed (Optimum Branchings), Super Dense MST
Parameters
$V$: number of vertices
$E$: number of edges
$U$: maximum edge weight
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Kruskal’s algorithm with demand-sorting | 1991 | $O(E \log V)$ | $O(E)$ | Exact | Deterministic | Time |
| Quick Kruskal algorithm | 2006 | $O(E \log V)$ | $O(E)$ | Exact | Deterministic | Time |
| Karger; Klein & Tarjan | 1995 | $O(min(V^{2}, ElogV)$) | $O(E)$ | Exact | Randomized | Time |
| Borůvka's algorithm | 1926 | $O(E \log V)$ | $O(V)$ auxiliary | Exact | Deterministic | |
| Prim's algorithm + adjacency matrix searching | 1957 | $O(V^{2})$ | $O(V)$ auxiliary | Exact | Deterministic | Time |
| Prim's algorithm + Fibonacci heaps; Fredman & Tarjan | 1987 | $O(E + V \log V)$ | $O(V)$ auxiliary? | Exact | Deterministic | Time |
| Kruskal's algorithm | 1956 | $O(E \log E)$ | $O(E)$ auxiliary | Exact | Deterministic | Time |
| Yao's algorithm | 1975 | $O(E \log \log V)$ | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Cheriton-Tarjan Algorithm | 1976 | $O(E \log \log V)$ | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Filter Kruskal algorithm | 2009 | $O(E \log V)$ | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Chazelle's algorithm | 2000 | $O(E*\alpha(E, V))$ | $O(E)$ auxiliary?? | Exact | Deterministic | Time |
| Thorup (reverse-delete) | 2000 | $O(E \log V (\log \log V)^{3})$ | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Bader & Cong Parallel Implementation | 2006 | $O(E \log(V)$/p) | $O(V)$ total | Exact | Parallel | Time |
| Prim's algorithm + binary heap | - | $O(ElogV)$ | $O(V)$ auxiliary? | Exact | Deterministic | |
| Fredman & Tarjan | 1987 | $O(E*beta(E, V)$) where beta(m, n) = min(i such that log^(i)(n)≤m/n); this is also $O(E (log-star)$V) | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Gabow et al, Section 2 | 1986 | $O(E*log(beta(E, V)$)) | $O(E)$ auxiliary? | Exact | Deterministic | Time |
| Pettie, Ramachandran | 2002 | unknown but optimal | $O(E)$ auxiliary? | Exact | Deterministic | Time |
Time Complexity Graph
_-_Undirected,_General_MST_-_Time.png)