Random minimum length spanning trees in regular graphs

DOI10.1007/PL00009825MaRDI QIDQ1288911zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Beveridge, Colin McDiarmid, Alan Frieze

Publication date 18 May 1999

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009825

zbMATH Keywords

expected minimum lengthrandom graphsrandom spanning treesregular connected graphs

Mathematics Subject Classification ID

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

Review text

For random graphs with edge lengths that are independently and uniformly distributed on the unit interval, the expected minimum length of a spanning forest is investigated. In particular, the expected minimum length of a spanning tree is given asymptotically for regular connected graphs.

Recommendations

• A note on random minimum length spanning trees
• On random minimum length spanning trees
• On the value of a random minimum spanning tree problem
• On the length of a random minimum spanning tree

Cited in

(37)

• A note on random minimum length spanning trees
• Geometry of the minimal spanning tree of a random 3-regular graph
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• A randomly weighted minimum spanning tree with a random cost constraint
• On the rank of a random binary matrix
• Fairest edge usage and minimum expected overlap for random spanning trees
• A concentration inequality for the facility location problem
• On the random 2-stage minimum spanning tree
• Minimum cost matching in a random graph with random costs
• Successive shortest paths in complete graphs with random edge weights
• On the difference of expected lengths of minimum spanning trees
• On the number of spanning trees in random regular graphs
• scientific article; zbMATH DE number 1123757 (Why is no real title available?)
• scientific article; zbMATH DE number 2066194 (Why is no real title available?)
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• Component structure of the vacant set induced by a random walk on a random graph
• The effect of adding randomly weighted edges
• Asymptotics in percolation on high-girth expanders
• Cross-Multiplicative Coalescent Processes and Applications
• On the length of a random minimum spanning tree
• The largest hole in sparse random graphs
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Site percolation on pseudo‐random graphs
• Supercritical site percolation on the hypercube: small components are small
• Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes
• Heavy and light paths and Hamilton cycles
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• Expansion in supercritical random subgraphs of expanders and its consequences
• Random minimum spanning tree and dense graph limits
• Colouring random subgraphs
• Minimum degree k and k-connectedness usually arrive together
• Coloring graphs from random lists
• Percolation on high-dimensional product graphs
• Percolation through isoperimetry
• Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
• Note on the structure of Kruskal's algorithm
• On random minimum length spanning trees

This page was built for publication: Random minimum length spanning trees in regular graphs

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