A network-flow technique for finding low-weight bounded-degree spanning trees

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning tree T using adoptions to meet the degree constraints is considered. A novel network-flow based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraint d(v) for each v is at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 − min n d(v)−2 degT (v)−2 : degT(v) > 2