Random costs C(i,j) are assigned to the area of a complete directed graph on n labeled vertices. Given the cost matrix Cn = (C(i,j)), let T−k* = T−k*(Cn) 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−ka. If the edge costs are independent, with a common exponential(1) distribution, then, as n→∞, E(Cost(T−ka)) = E(Cost(T−k*)) + o(1). Upper and lower bounds for E(Cost(T−k*)) are also obtained for k⩾2.
