Successive minimum spanning trees

DOI10.4230/LIPICS.APPROX-RANDOM.2019.60arXiv1906.01533MaRDI QIDQ6319955FDOQ6319955

Authors: Svante Janson, Gregory B. Sorkin

Publication date: 4 June 2019

Abstract: In a complete graph

K_{n}

with edge weights drawn independently from a uniform distribution

U (0, 1)

(or alternatively an exponential distribution

o p e r a t o r n a m e E x p (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

g a m m a_{k}

with

2 k - 2 s q r t k < g a m m a_{k} < 2 k + 2 s q r t k

, and we conjecture that

g a m m a_{k} = 2 k - 1 + o (1)

. The problem is distinct from that of Frieze and Johansson (2018), finding

k

MSTs of combined minimum weight, and for

k = 2

ours has strictly larger cost. 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

m a t h b b E (w (T_{k})) o g a m m a_{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

h o_{k} (t)

, uniformly for all

t

, and that a giant component appears in

F_{k} (t)

at a time

t = s i g m a_{k}

. We conjecture that the functions

h o_{k}

tend to time translations of a single function,

h o_{k} (2 k + x) o h o_{i} n f t y (x)

as

k o i n f t y

, uniformly in

x i n m a t h b b R

. Simulations and numerical computations give estimated values of

g a m m a_{k}

for small

k

, and support the conjectures just stated.

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

This page was built for publication: Successive minimum spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6319955)