Two-connected Steiner networks: structural properties

Pawel Winter, Martin Zachariasen

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)395-402
Number of pages8
JournalOperations Research Letters
Volume33
Issue number4
DOIs
Publication statusPublished - 2005

Keywords

  • survivable networks
  • 2-connected Steiner networks

Fingerprint

Dive into the research topics of 'Two-connected Steiner networks: structural properties'. Together they form a unique fingerprint.

Cite this