Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2006-012 (October 04, 2006)

Network design with edge-connectivity and degree constraints
by Takuro Fukunaga and Hiroshi Nagamoch

pdf File

We consider the following network design problem; Given a vertex set V with a metric cost c on V, a positive integer k, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v in V is equal to b(v). This problem generalizes metric TSP. In this paper, we propose that the problem admits a r-approximation algorithm if b(v) is at least 2, v in V, where r=2.5 if k is even, and r=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.