### Abstract

Random costs C(i, j) are assigned to the arcs of a complete directed graph on n labeled vertices. Given the cost matrix C_{n} = (C(i, J)), let T_{k}* = T_{k}*(C_{n}) be the spanning tree that has minimum cost among spanning trees with in-degree less than or equal to k. Since it is NP-hard to find T_{k}*, we instead consider an efficient algorithm that finds a near-optimal spanning tree T_{k}^{a}. If the edge costs are independent, with a common exponential(1) distribution, then, as n ? 8, E(Cost(T_{k}^{a}) = E(Cost(T_{k}*) + o(1). Upper and lower bounds for E(Cost(T_{k}*)) are also obtained for k = 2.

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

Pages (from-to) | 148-180 |

Number of pages | 33 |

Journal | Algorithmica |

Volume | 29 |

Issue number | 1-2 |

Publication status | Published - Jan 2001 |

### Keywords

- Approximation algorithm
- Assignment problem
- Random mapping
- Spanning tree

## Fingerprint Dive into the research topics of 'Near-optimal bounded-degree spanning trees'. Together they form a unique fingerprint.

## Cite this

Hansen, J. C., & Schmutz, E. (2001). Near-optimal bounded-degree spanning trees.

*Algorithmica*,*29*(1-2), 148-180.