On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph

Abstract: Assume that the edges of the complete graph

K_{n}

are given independent uniform

[0, 1]

edges weights. We consider the expected minimum total weight

m u_{k}

of

k g e q 2

edge disjoint spanning trees. When

k

is large we show that

m u_{k} a p p r o x k^{2}

. Most of the paper is concerned with the case

k = 2

. We show that

m_{2}

tends to an explicitly defined constant and that

m u_{2} a p p r o x 4.1704288 l d o t s

.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph