Access count of this item: 199

Files in This Item:
File Description SizeFormat 
s00224-008-9149-3.pdf214.14 kBAdobe PDFView/Open
Title: Network design with edge-connectivity and degree constraints
Authors: Fukunaga, Takuro
Nagamochi, Hiroshi  kyouindb  KAKEN_id
Author's alias: 福永, 拓郎
Keywords: (m, n)-VRP
Approximation algorithm
Degree constraint
Edge-connectivity
TSP
Vehicle routing problem
Issue Date: Oct-2009
Publisher: Springer Verlag
Journal title: Theory of Computing Systems
Volume: 45
Issue: 3
Start page: 512
End page: 532
Abstract: We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥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∈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)≥2, v∈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.
Rights: c Springer Science+Business Media, LLC 2008.
This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。
URI: http://hdl.handle.net/2433/87748
DOI(Published Version): 10.1007/s00224-008-9149-3
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.