A note on random minimum length spanning trees

MaRDI QIDQ1578476zbMATH OpenFDO

Authors Alan Frieze, Miklós Ruszinkó, Luboš Thoma

Publication date 14 September 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/120866, http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r41.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random edge lengthsspanning tree

Mathematics Subject Classification ID

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

Review text

The minimum length spanning tree is considered when edges have independent random lengths that are uniformly distributed on the unit interval. The asymptotic expected minimum length is obtained for regular graphs of increasing order.

Recommendations

• Random minimum length spanning trees in regular graphs
• 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
• scientific article; zbMATH DE number 3846542

Cited in

(20)

• On the value of a random minimum spanning tree problem
• Random minimum length spanning trees in regular graphs
• On average edge length of minimum spanning trees
• Minimum spanning trees of random geometric graphs with location dependent weights
• 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
• 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
• scientific article; zbMATH DE number 3846542 (Why is no real title available?)
• Approximations for the Random Minimal Spanning Tree with Application to Network Provisioning
• On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
• The effect of adding randomly weighted edges
• Notes on growing a tree in a graph
• On the length of a random minimum spanning tree
• Random graphs: combinatorics, complex networks and disordered systems. Abstracts from the workshop held March 26--31, 2023
• Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes
• Note on the structure of Kruskal's algorithm
• On random minimum length spanning trees

This page was built for publication: A note on random minimum length spanning trees

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