betaFeedback

WorksComputer Science

The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph

Abstract

Let GnG_n be a random weighted complete graph on nn vertices, where edges have i.i.d. Unif(0,1)\text{Unif}(0,1) weights. Let TnT_n be the Minimum Spanning Tree (MST) of GnG_n. The expected weight of TnT_n is known to converge to ζ(3)=∑k=1∞1k3ζ(3) = \sum_{k=1}^{\infty} \frac{1}{k^3} (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of TnT_n, denoting this quantity by LnL_n. We give tight upper and lower bounds on E[Ln]\mathbb{E}[L_n] and determine its limit as nn diverges, leveraging typical behavior of sparse Erdős–Rényi random graphs. We also establish concentration of LnL_n around E[Ln]\mathbb{E}[L_n] and almost sure convergence to this value. These results directly yield substantial improvements to state-of-the-art bounds for two important variants of the MST problem: (1) an improved upper bound on the weight of the optimal random instance Steiner tree, as studied by Bollobás, Gamarnik, Riordan, and Sudakov (2004); and (2) an improvement over the upper bound for the Probabilistic Minimum Spanning Tree, introduced by Bertsimas (1988).

Paper details

vlnc:W_qw9f3fmp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…