Approximating a Generalization of Metric TSP

Takuro FUKUNAGA  Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E90-D   No.2   pp.432-439
Publication Date: 2007/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e90-d.2.432
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithms
Keyword: 
approximation algorithm,  edge-connectivity,  degree specification,  graph algorithm,  metric,  network design,  TSP,  

Full Text: PDF(376.3KB)>>
Buy this Article




Summary: 
We consider a problem for constructing a minimum cost r-edge-connected multigraph in which degree d(v) of each vertex vV is specified. In this paper, we propose a 3-approximation algorithm for this problem under the assumption that edge cost is metric, r(u,v) ∈ {1,2} for each u,vV, and d(v) ≥ 2 for each vV. This problem is a generalization of metric TSP. We also propose an approximation algorithm for the digraph version of the problem.