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
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={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
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={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
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={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
ER -