2002年2月
A note on approximating the survivable network design problem in hypergraphs
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
- ,
- ,
- 巻
- E85D
- 号
- 2
- 開始ページ
- 322
- 終了ページ
- 326
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- 出版者・発行元
- IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG. by replacing each hyperedge e = {v(1),...,v(k)} with a new vertex omega(e) and k edges {omega(e),nu(1)},...,{omega(e),nu(k)} we define an SNDP or ECP in the resulting graph. We show that by approximately solving the. SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a d(max)(+)-approximation algorithm for the SNDPHG with d(max) less than or equal to 3, where d(max) (resp. d(max)(+)) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d(max)(+)H(r(max))-approximation algorithm for the SNDPHG, where H(i) = Sigma(j=1)(l) 1/j is the harmonic function and r(max) is the maximum connectivity requirement.
- リンク情報
- ID情報
-
- ISSN : 1745-1361
- J-Global ID : 200902155761388784
- Web of Science ID : WOS:000173950900003