### Abstract

Suppose that script C = {c_{ij} : i, j = 1} is a collection of i.i.d. nonnegative continuous random variables and suppose T is a rooted, directed tree on vertices labelled 1,2,. . . ,n. Then the 'cost' of T is denned to be c(T) = S _{(i,j)?T} c_{ij}, where (i, j) denotes the directed edge from i to j in the tree T. Let T_{n} denote the 'optimal' tree, i.e. c(T_{n})=min{c(T) : T is a directed, rooted tree in with n vertices}. We establish general conditions on the asymptotic behaviour of the moments of the order statistics of the variables c_{11}, c_{12},. . . , c_{in} which guarantee the existence of sequences {a_{n}}, {b_{n}}, and {d_{n}} such that b^{-1}_{n}(c(T_{n})-a_{n}) ? N(0, 1) in distribution, d^{-1}_{n} c(T_{n}) ? 1 in probability, and d^{-1}_{n}E(c(T_{n})) ? 1 as n ? 8, and we explicitly determine these sequences. The proofs of the main results rely upon the properties of general random mappings of the set {1, 2, . . . , n} into itself. Our results complement and extend those obtained by McDiarmid [9] for optimal branchings in a complete directed graph.

Original language | English |
---|---|

Pages (from-to) | 315-335 |

Number of pages | 21 |

Journal | Combinatorics, Probability and Computing |

Volume | 6 |

Issue number | 3 |

Publication status | Published - 1997 |