2009年10月
Network Design with Edge-Connectivity and Degree Constraints
THEORY OF COMPUTING SYSTEMS
- ,
- 巻
- 45
- 号
- 3
- 開始ページ
- 512
- 終了ページ
- 532
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/s00224-008-9149-3
- 出版者・発行元
- SPRINGER
We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer ka parts per thousand yen1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex vaV is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a rho-approximation algorithm if b(v)a parts per thousand yen2, vaV, where rho=2.5 if k is even, and rho=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.
- リンク情報
-
- DOI
- https://doi.org/10.1007/s00224-008-9149-3
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902254323249729
- CiNii Articles
- http://ci.nii.ac.jp/naid/120001712074
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000267899000007&DestApp=WOS_CPL
- ID情報
-
- DOI : 10.1007/s00224-008-9149-3
- ISSN : 1432-4350
- eISSN : 1433-0490
- J-Global ID : 200902254323249729
- CiNii Articles ID : 120001712074
- Web of Science ID : WOS:000267899000007