Random Minimum Length Spanning Trees in Regular Graphs |
| |
| Authors: | Andrew Beveridge Alan Frieze Colin McDiarmid |
| |
| Affiliation: | (1) Department of Mathematical Sciences, Carnegie Mellon University, US;(2) Department of Mathematical Sciences, Carnegie Mellon University; E-mail: alan@random.math.cmu.edu, US;(3) Department of Statistics, University of Oxford; E-mail: cmcd@stats.ox.ac.uk, UK |
| |
| Abstract: | r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that . Received: Februray 9, 1998 |
| |
| Keywords: | AMS Subject Classification (1991) Classes: 05C80, 60C05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
