The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

DOI10.1002/rsa.3240070406zbMath0844.05085MaRDI QIDQ4858241

Svante Janson

Publication date: 12 December 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240070406

zbMATH Keywords

normal distribution; limit theorem; spanning tree; random graph; random weights

Mathematics Subject Classification ID

05C05: Trees

05C80: Random graphs (graph-theoretic aspects)

60F17: Functional limit theorems; invariance principles

Related Items

On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph, Cross-Multiplicative Coalescent Processes and Applications, On the Length of a Random Minimum Spanning Tree, Diameter of the Stochastic Mean-Field Model of Distance, Unnamed Item, Successive minimum spanning trees, Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes, Models of random subtrees of a graph, Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes, A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, Coalescent random forests, Tail bound for the minimal spanning tree of a complete graph., The central limit theorem for weighted minimal spanning trees on random points, Asymptotics of integrals of Betti numbers for random simplicial complex processes, Geometry of the minimal spanning tree of a random 3-regular graph, Typical values of extremal-weight combinatorial structures with independent symmetric weights, A randomly weighted minimum spanning tree with a random cost constraint, Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs, On the rank of a random binary matrix, On the number of isolated vertices in a growing random graph, Local tail bounds for functions of independent random variables, Monotonicity, asymptotic normality and vertex degrees in random graphs, A concentration inequality for the facility location problem, Minimum Cost Matching in a Random Graph with Random Costs, The order of the giant component of random hypergraphs, Weight of a link in a shortest path tree and the Dedekind Eta function, On finding a minimum spanning tree in a network with random weights, On the Difference of Expected Lengths of Minimum Spanning Trees

Cites Work

• Unnamed Item