On Shortest k-Edge-Connected Steiner Networks in Metric Spaces

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)99-107
Journal / PublicationJournal of Combinatorial Optimization
Volume4
Issue number1
Publication statusPublished - 2000

Abstract

Given a set of points P in a metric space, let lk (P) denote the ratio of lengths between the shortest k-edge-connected Steiner network and the shortest k-edge-connected spanning network on P, and let rk = inf{lk(P)|P} for k ≥ 1. In this paper, we show that in any metric space, rk ≥ 3/4 for k ≥ 2, and there exists a polynomial-time α-approximation for the shortest k-edge-connected Steiner network, where α = 2 for even k and α = 2 + 4/(3k) for odd k. In the Euclidean plane, rk ≥ √3/2, r3 ≤ (√3+2)/4 and r4 ≤ (7+3√3)/(9+2√3).

Research Area(s)

  • K-edge-connectivity, Spanning networks, Steiner networks, Steiner ratio

Citation Format(s)

On Shortest k-Edge-Connected Steiner Networks in Metric Spaces. / Du, Xiufeng; Hu, Xiaodong; Jia, Xiaohua.

In: Journal of Combinatorial Optimization, Vol. 4, No. 1, 2000, p. 99-107.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review