Premium
Successive minimum spanning trees
Author(s) -
Janson Svante,
Sorkin Gregory B.
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21047
Subject(s) - combinatorics , spanning tree , mathematics , minimum spanning tree , conjecture , weight function , minimum degree spanning tree , disjoint sets , enhanced data rates for gsm evolution , minimum weight , kruskal's algorithm , graph , exponential function , tree (set theory) , discrete mathematics , computer science , statistics , telecommunications , mathematical analysis
In a complete graphK nwith independent uniform ( 0 , 1 ) (or exponential ( 1 ) ) edge weights, letT 1be the minimum‐weight spanning tree (MST), andT kthe MST after deleting the edges of all previous trees. We show that each tree's weight w ( T k ) converges in probability to a constantγ k, with 2 k − 2 k < γ k < 2 k + 2 k, and we conjecture thatγ k = 2 k − 1 + o ( 1 ) . The problem is distinct from Frieze and Johansson's minimum combined weightμ kof k edge‐disjoint spanning trees; indeed,μ 2 < γ 1 + γ 2. With an edge of weight w “arriving” at time t = n w , Kruskal's algorithm defines forestsF k ( t ) , initially empty and eventually equal toT k, each edge added to the first possibleF k ( t ) . Using tools of inhomogeneous random graphs we obtain structural results including that the fraction of vertices in the largest component ofF k ( t ) converges to someρ k ( t ) . We conjecture that the functionsρ ktend to time translations of a single function.