Name
Abstract | ||
|---|---|---|
Consider a connected r-regular n-vertex graph G with random independent edgelengths, each uniformly distributed on (0; 1). Let mst(G) be the expected length ofa minimum spanning tree. We show that mst(G) can be estimated quite accuratelyunder two distinct circumstances. Firstly, if r is large and G has a modest edgeexpansion property then mst(G) ?nri(3), where i(3) =P 1j=1 j\Gamma3? 1:202. Secondly,if G has large girth then there exists an explicitly defined constant c r such... |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/PL00009825 | Combinatorica |
Keywords | Field | DocType |
spanning tree,regular graph,minimum spanning tree | Graph,Discrete mathematics,Combinatorics,Minimum degree spanning tree,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
18 | 3 | 0209-9683 |
Citations | PageRank | References |
17 | 1.32 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Colin McDiarmid | 3 | 1071 | 167.05 |