Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Janson, Svante; Sorkin, Gregory B. https://www.dagstuhl.de/lipics 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},
  address =	{Dagstuhl, Germany},
  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
Seminar: 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 Published by LZI