論文

査読有り
2009年10月

Network Design with Edge-Connectivity and Degree Constraints

THEORY OF COMPUTING SYSTEMS
  • Takuro Fukunaga
  • ,
  • Hiroshi Nagamochi

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

エクスポート
BibTeX RIS