The search functionality is under construction.
The search functionality is under construction.

A Note on Approximating the Survivable Network Design Problem in Hypergraphs

Liang ZHAO, Hiroshi NAGAMOCHI, Toshihide IBARAKI

  • Full Text Views

    0

  • Cite this

Summary :

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={v1,・・・,vk} with a new vertex we and k edges {we, v1},・・・, {we, vk}, 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 dmax+-approximation algorithm for the SNDPHG with dmax 3, where dmax (resp. dmax+) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a dmax+(rmax)-approximation algorithm for the SNDPHG, where (i)=j=1i(1/j) is the harmonic function and rmax is the maximum connectivity requirement.

Publication
IEICE TRANSACTIONS on Information Vol.E85-D No.2 pp.322-326
Publication Date
2002/02/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category

Authors

Keyword