## Abstract

We consider the problem of constructing a minimum-length 2-connected network for a set of

terminals in a graph where edge-weights satisfy the triangle inequality. As a special case of the

problem, we have the Euclidean 2-connected Steiner network problem in which a set of points in

the plane should be interconnected by a 2-connected network of minimum length. These problems

have natural applications in the design of surviable communication networks.

In this paper we give a number of structural results for the problem. We show that all cycles

must have at least four terminals, and that these terminals must be distributed in groups of two. Furthermore, we give a tight lower bound on the minimum size of any problem instance that requires

a Steiner vertex.

terminals in a graph where edge-weights satisfy the triangle inequality. As a special case of the

problem, we have the Euclidean 2-connected Steiner network problem in which a set of points in

the plane should be interconnected by a 2-connected network of minimum length. These problems

have natural applications in the design of surviable communication networks.

In this paper we give a number of structural results for the problem. We show that all cycles

must have at least four terminals, and that these terminals must be distributed in groups of two. Furthermore, we give a tight lower bound on the minimum size of any problem instance that requires

a Steiner vertex.

Original language | English |
---|---|

Pages (from-to) | 395-402 |

Number of pages | 8 |

Journal | Operations Research Letters |

Volume | 33 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2005 |

## Keywords

- survivable networks
- 2-connected Steiner networks