The search functionality is under construction.

The search functionality is under construction.

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} *d*_{max} (resp. *d*_{max}^{+}) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a *d*_{max}^{+}*r*_{max})-approximation algorithm for the SNDPHG, where *i*)=_{j=1}^{i}(1/j) is the harmonic function and *r*_{max} 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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Liang ZHAO, Hiroshi NAGAMOCHI, Toshihide IBARAKI, "A Note on Approximating the Survivable Network Design Problem in Hypergraphs" in IEICE TRANSACTIONS on Information,
vol. E85-D, no. 2, pp. 322-326, February 2002, doi: .

Abstract: 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} *d*_{max} (resp. *d*_{max}^{+}) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a *d*_{max}^{+}*r*_{max})-approximation algorithm for the SNDPHG, where *i*)=_{j=1}^{i}(1/j) is the harmonic function and *r*_{max} is the maximum connectivity requirement.

URL: https://global.ieice.org/en_transactions/information/10.1587/e85-d_2_322/_p

Copy

@ARTICLE{e85-d_2_322,

author={Liang ZHAO, Hiroshi NAGAMOCHI, Toshihide IBARAKI, },

journal={IEICE TRANSACTIONS on Information},

title={A Note on Approximating the Survivable Network Design Problem in Hypergraphs},

year={2002},

volume={E85-D},

number={2},

pages={322-326},

abstract={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} *d*_{max} (resp. *d*_{max}^{+}) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a *d*_{max}^{+}*r*_{max})-approximation algorithm for the SNDPHG, where *i*)=_{j=1}^{i}(1/j) is the harmonic function and *r*_{max} is the maximum connectivity requirement.

keywords={},

doi={},

ISSN={},

month={February},}

Copy

TY - JOUR

TI - A Note on Approximating the Survivable Network Design Problem in Hypergraphs

T2 - IEICE TRANSACTIONS on Information

SP - 322

EP - 326

AU - Liang ZHAO

AU - Hiroshi NAGAMOCHI

AU - Toshihide IBARAKI

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E85-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 2002

AB - 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} *d*_{max} (resp. *d*_{max}^{+}) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a *d*_{max}^{+}*r*_{max})-approximation algorithm for the SNDPHG, where *i*)=_{j=1}^{i}(1/j) is the harmonic function and *r*_{max} is the maximum connectivity requirement.

ER -