Network design with weighted degree constraints

Abstract

In an undirected graph G = (V, E) with a weight function w : E × V → Q+, the weighted degree dw(v;E) of a vertex v is defined as Σ{w(e, v)｜e ∈ E incident to v}. In this paper, we consider a network design problem which has upper-bounds on weighted degrees of vertices as its constraints while the objective is to compute a minimum cost graph with a prescribed connectivity. We propose bi-criteria approximation algorithms based on the iterative round-ing, which has been successfully applied to the degree-bounded network design problem. A problem of minimizing the maximum weighted degree of vertices is also discussed.