論文

査読有り
2002年2月

A Note on Approximating the Survivable Network Design Problem in Hypergraphs(<特集>Special Issue on Selected Papers from LA Symposium)

IEICE transactions on information and systems
  • ZHAO Liang
  • ,
  • NAGAMOCHI Hiroshi
  • ,
  • IBARAKI Toshihide

85
2
開始ページ
322
終了ページ
326
記述言語
英語
掲載種別
研究論文(学術雑誌)
出版者・発行元
一般社団法人電子情報通信学会

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 w_e and k edges {w_e,v_1}, ..., {w_e,v_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^+_&lt;max&gt;-approximation algorithm for the SNDPHG with d_&lt;max&gt; &amp;le; 3, where d_&lt;max&gt; (resp. d^+_&lt;max&gt;) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d^+_&lt;max&gt;H(r_&lt;max&gt;)-approximation algorithm for the SNDPHG, where H(i) = ?^i_&lt;j=1&gt; 1/j is the harmonic function and r_&lt;max&gt; is the maximum connectivity requirement.

リンク情報
CiNii Articles
http://ci.nii.ac.jp/naid/110003219881
CiNii Books
http://ci.nii.ac.jp/ncid/AA10826272
ID情報
  • ISSN : 0916-8532
  • CiNii Articles ID : 110003219881
  • CiNii Books ID : AA10826272
  • identifiers.cinii_nr_id : 9000004870179

エクスポート
BibTeX RIS