World Colleges Information

Given a complete graph with edge weights satisfying the triangle inequality,and a degree bound for each vertex, we consider the problem of computing a low-weight spanning tree in which the degree of each vertex is at most its given bound.