論文

査読有り
2002年2月

A note on approximating the survivable network design problem in hypergraphs

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
  • L Zhao
  • ,
  • H Nagamochi
  • ,
  • T Ibaraki

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.

リンク情報
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902155761388784
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000173950900003&DestApp=WOS_CPL
ID情報
  • ISSN : 1745-1361
  • J-Global ID : 200902155761388784
  • Web of Science ID : WOS:000173950900003

エクスポート
BibTeX RIS