On the value of a random minimum spanning tree problem

DOI10.1016/0166-218X(85)90058-7MaRDI QIDQ1066149zbMATH OpenDBLPWikidataFDO

Authors Alan Frieze

Publication date 1985

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(85)90058-7

zbMATH Keywords

complete graphedge lengthminimum spanning tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Review text

The lengths of the edges in a complete graph of order n are independent identically distributed random variables. Under mild conditions the length of the minimum spanning tree is shown to converge in probability as \(n\to \infty\), and the limiting value of the expected length is determined.

Recommendations

• On random minimum length spanning trees
• On the length of a random minimum spanning tree
• A note on random minimum length spanning trees
• scientific article; zbMATH DE number 4056658
• scientific article; zbMATH DE number 3846542

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• On the connectivity of random m-orientable graphs and digraphs
• On the Expected Value of a Random Assignment Problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimization Problems on Graphs with Independent Random Edge Weights

Cited in

(91)

• On Frieze's (3) limit for lengths of minimal spanning trees
• Random minimum length spanning trees in regular graphs
• Tail bound for the minimal spanning tree of a complete graph.
• A note on random minimum length spanning trees
• On average edge length of minimum spanning trees
• Asymptotics for weighted minimal spanning trees on random points
• The scaling limit of the minimum spanning tree of the complete graph
• Gaussian tail for empirical distributions of MST on random graphs
• All-pairs shortest paths and the essential subgraph
• On the probabilistic min spanning tree problem
• Weak disorder in the stochastic mean-field model of distance. II
• Limit theorems for random cubical homology
• 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
• 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
• GHS algorithm on a graph with random weights
• Minimum-weight combinatorial structures under random cost-constraints
• 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
• Extremal paths in inhomogenous random graphs
• On the rank of a random binary matrix
• Asymptotic behavior of lifetime sums for random simplicial complex processes
• Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles
• On the longest path of a randomly weighted tournament
• Weak disorder asymptotics in the stochastic mean-field model of distance
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
• Local tail bounds for functions of independent random variables
• A concentration inequality for the facility location problem
• The (2) limit in the random assignment problem
• A survey on combinatorial optimization in dynamic environments
• The expected value of random minimal length spanning tree of a complete graph
• On the random 2-stage minimum spanning tree
• Minimum cost matching in a random graph with random costs
• Critical random graphs and the structure of a minimum spanning tree
• Weight of a link in a shortest path tree and the Dedekind eta function
• Edge flows in the complete random-lengths network
• On finding a minimum spanning tree in a network with random weights
• Probabilistic analysis of an algorithm for the minimum spanning tree problem with diameter bounded below
• scientific article; zbMATH DE number 3846542 (Why is no real title available?)
• Successive shortest paths in complete graphs with random edge weights
• Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points
• The probabilistic minimum spanning tree problem
• On the difference of expected lengths of minimum spanning trees
• scientific article; zbMATH DE number 4056658 (Why is no real title available?)
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• Replica symmetry of the minimum matching
• Limit Laws for the Optimal Directed Tree with Random Costs
• scientific article; zbMATH DE number 1984546 (Why is no real title available?)
• scientific article; zbMATH DE number 2065879 (Why is no real title available?)
• scientific article; zbMATH DE number 2066194 (Why is no real title available?)
• A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks
• Bounds for random binary quadratic programs
• Renewal sequences and record chains related to multiple zeta sums
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• On the greedy algorithm with random costs
• Belief propagation for optimal edge cover in the random complete graph
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Spanning-tree games
• Partition functions of discrete coalescents: from Cayley's formula to Frieze's (3) limit theorem
• The random QUBO
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• Cross-Multiplicative Coalescent Processes and Applications
• Efficient algorithms for three‐dimensional axial and planar random assignment problems
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty
• On the length of a random minimum spanning tree
• Diameter of the stochastic mean-field model of distance
• Maximal Steiner trees in the stochastic mean-field model of distance
• Sorting and Selection with Random Costs
• A survey of max-type recursive distributional equations
• Minimum weight disk triangulations and fillings
• scientific article; zbMATH DE number 7650127 (Why is no real title available?)
• 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
• The mean field traveling salesman and related problems
• Models of random subtrees of a graph
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• The wired minimal spanning forest on the Poisson-weighted infinite tree
• On minimum spanning trees for random Euclidean bipartite graphs
• Edge-disjoint spanning trees of arbitrary bounded diameter on random inputs
• Minimum spanning trees of random geometric graphs with independent edge weights
• Random minimum spanning tree and dense graph limits
• Noise sensitivity of the minimum spanning tree of the complete graph
• A generalization of the Beraha-Kahane-Weiss theorem with graph polynomial applications
• Weighted tree games
• Minimal H-factors and covers
• On the value of a random minimum weight Steiner tree
• Note on the structure of Kruskal's algorithm
• The lower tail of the random minimum spanning tree
• On random minimum length spanning trees

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

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