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

概要

論文の詳細を見る
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^+_<max>-approximation algorithm for the SNDPHG with d_<max> ≤ 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) = ？^i_<j=1> 1/j is the harmonic function and r_<max> is the maximum connectivity requirement.
社団法人電子情報通信学会の論文
2002-02-01