On the length of a random minimum spanning tree

DOI10.1017/S0963548315000024MaRDI QIDQ5364266zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Colin Cooper, Nate Ince, Svante Janson, Alan Frieze, Joel Spencer

Publication date 4 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.5170

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35)

Abstract: We study the expected value of the length $L_n$ of the minimum spanning tree of the complete graph $K_n$ when each edge $e$ is given an independent uniform $[0,1]$ edge weight. We sharpen the result of Frieze cite{F1} that $li{m}_{noinfty}E(L_n)=z(3)$ and show that $E(L_n)=z(3)+frac{c}_{1}n+frac{c}_2+o(1)n^{4/3}$ where $c_1,c_2$ are explicitly defined constants.

Recommendations

• On the value of a random minimum spanning tree problem
• On random minimum length spanning trees
• On Frieze's (3) limit for lengths of minimal spanning trees
• A note on random minimum length spanning trees
• scientific article; zbMATH DE number 4056658

Cites work

• scientific article; zbMATH DE number 3152798 (Why is no real title available?)
• scientific article; zbMATH DE number 1123759 (Why is no real title available?)
• scientific article; zbMATH DE number 1984546 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution
• A note on random minimum length spanning trees
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• Enumerating graphs and Brownian motion
• Kac's formula, levy's local time and brownian excursion
• Multicyclic components in a random graph process
• On Frieze's (3) limit for lengths of minimal spanning trees
• On random minimum length spanning trees
• On the difference of expected lengths of minimum spanning trees
• On the value of a random minimum spanning tree problem
• Paths in graphs
• Polynomial representation for the expected length of minimal spanning trees
• Random minimum length spanning trees in regular graphs
• Tail estimates for the Brownian excursion area and other Brownian areas
• The Brownian excursion area: A numerical analysis
• The birth of the giant component
• The center of mass of the ISE and the Wiener index of trees
• The expected value of random minimal length spanning tree of a complete graph
• The lower tail of the random minimum spanning tree
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The number of connected sparsely edged graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(41)

• Critical random graphs and the structure of a minimum spanning tree
• Minimum spanning trees of random geometric graphs with location dependent weights
• A concentration inequality for the facility location problem
• scientific article; zbMATH DE number 7650127 (Why is no real title available?)
• scientific article; zbMATH DE number 1984546 (Why is no real title available?)
• Several edge-disjoint spanning trees with given diameter in a graph with random discrete edge weights
• Partition functions of discrete coalescents: from Cayley's formula to Frieze's (3) limit theorem
• On average edge length of minimum spanning trees
• Typical values of extremal-weight combinatorial structures with independent symmetric weights
• scientific article; zbMATH DE number 3846542 (Why is no real title available?)
• Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes
• Random-tree diameter and the diameter-constrained MST
• On asymptotically optimal approach for the problem of finding several edge-disjoint spanning trees of given diameter in an undirected graph with random edge weights
• An upper bound for the average length of the euclidean minimum spanning tree
• scientific article; zbMATH DE number 4056658 (Why is no real title available?)
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• On the difference of expected lengths of minimum spanning trees
• Successive minimum spanning trees
• Polynomial representation for the expected length of minimal spanning trees
• Random-tree Diameter and the Diameter-constrained MST
• Tail bound for the minimal spanning tree of a complete graph.
• The lower tail of the random minimum spanning tree
• Cross-Multiplicative Coalescent Processes and Applications
• Probability on a complete graph: uniform and minimal spanning trees
• On the value of a random minimum spanning tree problem
• On the random 2-stage minimum spanning tree
• On random minimum length spanning trees
• On Frieze's (3) limit for lengths of minimal spanning trees
• The expected value of random minimal length spanning tree of a complete graph
• Models of random subtrees of a graph
• On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter
• Minimum cost matching in a random graph with random costs
• On the longest path of a randomly weighted tournament
• A randomly weighted minimum spanning tree with a random cost constraint
• A generalization of the Beraha-Kahane-Weiss theorem with graph polynomial applications
• scientific article; zbMATH DE number 1123759 (Why is no real title available?)
• scientific article; zbMATH DE number 2065879 (Why is no real title available?)
• Spanning-tree games
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• Minimum spanning acycle and lifetime of persistent homology in the Linial-Meshulam process
• The Expected Length of a Minimal Spanning Tree of a Cylinder Graph

This page was built for publication: On the length of a random minimum spanning tree

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