Minimum weight spanning trees with random costs

Minimum weight spanning trees with random costs

Probability Seminar
Mar 30, 2016, 03:10 PM - 12:00 AM | 1011 Evans Hall | Happening As Scheduled
Alan Frieze, Department of Mathematical Sciences, Carnegie Mellon University (Speaker)
We discuss some old and new results on the following problem. Given a graph with independent uniform [0,1] random edge weights, what can we say about the length of the minimum spanning tree.