On the Length of a Random Minimum Spanning Tree

DOI10.1017/S0963548315000024zbMath1371.05260arXiv1208.5170OpenAlexW3104366618WikidataQ57401404 ScholiaQ57401404MaRDI QIDQ5364266

Nate Ince, Svante Janson, Colin Cooper, J. H. Spencer, Alan M. Frieze

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

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

Related Items

On the longest path of a randomly weighted tournament, A concentration inequality for the facility location problem, Successive minimum spanning trees, On asymptotically optimal approach for finding of the minimum total weight of edge-disjoint spanning trees with a given diameter, Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes, Unnamed Item, Models of random subtrees of a graph, Minimum Cost Matching in a Random Graph with Random Costs, A randomly weighted minimum spanning tree with a random cost constraint, Spanning-Tree Games., On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph, Cross-Multiplicative Coalescent Processes and Applications, Typical values of extremal-weight combinatorial structures with independent symmetric weights, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The lower tail of the random minimum spanning tree
• On random minimum length spanning trees
• Brownian excursion area, wright's constants in graph enumeration, and other Brownian areas
• An easy proof of the \(\zeta (2)\) limit in the random assignment problem
• Tail estimates for the Brownian excursion area and other Brownian areas
• The Brownian excursion area: A numerical analysis
• On the value of a random minimum spanning tree problem
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• Random minimum length spanning trees in regular graphs
• A note on random minimum length spanning trees
• The center of mass of the ISE and the Wiener index of trees
• Kac's formula, levy's local time and brownian excursion
• On the Difference of Expected Lengths of Minimum Spanning Trees
• Multicyclic components in a random graph process
• The number of connected sparsely edged graphs
• Enumerating graphs and Brownian motion
• Paths in graphs
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Polynomial representation for the expected length of minimal spanning trees
• The birth of the giant component
• A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution