 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-112759
URL:

;

### Successive Minimum Spanning Trees

 pdf-format:

### Abstract

In a complete graph K_n with edge weights drawn independently from a uniform distribution U(0,1) (or alternatively an exponential distribution 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<k. We show that each tree's weight w(T_k) converges in probability to a constant gamma_k with 2k-2 sqrt k < gamma_k < 2k+2 sqrt k, and we conjecture that gamma_k = 2k-1+o(1). The problem is distinct from that of [Alan Frieze and Tony Johansson, 2018], finding k MSTs of combined minimum weight, and the combined cost for two trees in their problem is, asymptotically, strictly smaller than our gamma_1+gamma_2. Our results also hold (and mostly are derived) in a multigraph model where edge weights for each vertex pair follow a Poisson process; here we additionally have E(w(T_k)) -> gamma_k. Thinking of an edge of weight w as arriving at time t=n w, Kruskal's algorithm defines forests F_k(t), each initially empty and eventually equal to T_k, with each arriving edge added to the first F_k(t) where it does not create a cycle. Using tools of inhomogeneous random graphs we obtain structural results including that C_1(F_k(t))/n, the fraction of vertices in the largest component of F_k(t), converges in probability to a function rho_k(t), uniformly for all t, and that a giant component appears in F_k(t) at a time t=sigma_k. We conjecture that the functions rho_k tend to time translations of a single function, rho_k(2k+x) -> rho_infty(x) as k -> infty, uniformly in x in R. Simulations and numerical computations give estimated values of gamma_k for small k, and support the conjectures stated above.

### BibTeX - Entry

```@InProceedings{janson_et_al:LIPIcs:2019:11275,
author =	{Svante Janson and Gregory B. Sorkin},
title =	{{Successive Minimum Spanning Trees}},
booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
pages =	{60:1--60:16},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-125-2},
ISSN =	{1868-8969},
year =	{2019},
volume =	{145},
editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 