Successive minimum spanning trees
| Autor: | Svante Janson, Gregory B. Sorkin |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Random graph
000 Computer science knowledge general works Spanning tree Applied Mathematics General Mathematics Multigraph Probability (math.PR) Complete graph Minimum spanning tree Computer Graphics and Computer-Aided Design Giant component Vertex (geometry) Combinatorics Kruskal's algorithm Computer Science FOS: Mathematics Mathematics - Combinatorics QA Mathematics Combinatorics (math.CO) Computer Science::Data Structures and Algorithms 05C80 60C05 05C22 68W40 Mathematics - Probability Software Mathematics |
| DOI: | 10.48550/arxiv.1906.01533 |
| Popis: | In a complete graph $K_n$ with edge weights drawn independently from a uniform distribution $U(0,1)$ (or alternatively an exponential distribution $\operatorname{Exp}(1)$), let $T_1$ be the MST (the spanning tree of minimum weight) and let $T_k$ be the MST after deletion of the edges of all previous trees $T_i$, $i |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|