On random minimum length spanning trees

DOI10.1007/BF02125348zbMath0712.05050OpenAlexW2052882549WikidataQ57401607 ScholiaQ57401607MaRDI QIDQ923108

Colin J. H. McDiarmid, Alan M. Frieze

Publication date: 1989

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

minimum spanning treerandom edge lengths

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80)

Related Items (14)

A concentration inequality for the facility location problem ⋮ Successive minimum spanning trees ⋮ Geometry of the minimal spanning tree in the heavy-tailed regime: new universality classes ⋮ On the Length of a Random Minimum Spanning Tree ⋮ A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ A randomly weighted minimum spanning tree with a random cost constraint ⋮ On the Difference of Expected Lengths of Minimum Spanning Trees ⋮ On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph ⋮ Improved approximation results for the minimum energy broadcasting problem ⋮ Critical random graphs and the structure of a minimum spanning tree ⋮ On finding a minimum spanning tree in a network with random weights ⋮ Geometry of the minimal spanning tree of a random 3-regular graph ⋮ Cross-Multiplicative Coalescent Processes and Applications ⋮ Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks

Cites Work

• On the value of a random minimum spanning tree problem
• On Frieze's \(\zeta\) (3) limit for lengths of minimal spanning trees
• On the greedy algorithm with random costs
• Unnamed Item
• Unnamed Item

This page was built for publication: On random minimum length spanning trees