When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.60
URN: urn:nbn:de:0030-drops-112759
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11275/
 Go to the corresponding LIPIcs Volume Portal

### 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},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11275},
URN =		{urn:nbn:de:0030-drops-112759},
doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.60},
annote =	{Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type bra}
}
```

 Keywords: miminum spanning tree, second-cheapest structure, inhomogeneous random graph, optimization in random structures, discrete probability, multi-type bra Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) Issue Date: 2019 Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy