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)

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)