History
Year:
-
Type:
Journal
Book
Article
Please fill in your query. A complete syntax description you will find on the General Help page.
Network design with edge-connectivity and degree constraints. (English)
Theory Comput. Syst. 45, No. 3, 512-532 (2009).
Summary: We consider the following network design problem; Given a vertex set $V$ with a metric cost $c$ on $V$, an integer $k\geq 1$, 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 show that the problem admits a $ρ$-approximation algorithm if $b(v)\geq 2, v\in V$, where $ρ=2.5$ if $k$ is even, and $ρ=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.
WorldCat.org
Valid XHTML 1.0 Transitional Valid CSS!