A Note on Approximating the Survivable Network Design Problem in Hypergraphs

Liang ZHAO  Hiroshi NAGAMOCHI  Toshihide IBARAKI 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E85-D  No.2  pp.322-326
Publication Date: 2002/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
survivable network design problem,  approximation algorithm,  connectivity,  graph,  hypergraph, 

Full Text: PDF(371.8KB)

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.