The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with host publication)peer-review

27 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication7th Annual International Conference, COCOON 2001, Proceedings
EditorsJie Wang
PublisherSpringer Verlag
Pages509-518
Volume2108
ISBN (Print)9783540424949
Publication statusPublished - 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2108
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Title7th Annual International Conference on Computing and Combinatorics, COCOON 2001
PlaceChina
CityGuilin
Period20 - 23 August 2001

Abstract

We study variations of Steiner tree problem. Let P = {p1, p2,…, pn} be a set of n terminals in the Euclidean plane. For a positive integer k, the bottleneck Steiner tree problem (BSTP for short) is to find a Steiner tree with at most k Steiner points such that the length of the longest edges in the tree is minimized. For a positive constant R, the Steiner tree problem with minimum number of Steiner points (STP − MSP for short) asks for a Steiner tree such that each edge in the tree has length at most R and the number of Steiner points is minimized. In this paper, we give (1) a ratio- √ 3 + ε approximation algorithm for BSTP, where ε is an arbitrary positive number; (2) a ratio-3 approximation algorithm for STP-MSP with running time O(n3); (3) a ratio-5/2 approximation algorithm for STP-MSP.

Citation Format(s)

The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. / Du, Dingzhu; Wang, Lusheng; Xu, Baogang.
Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Proceedings. ed. / Jie Wang. Vol. 2108 Springer Verlag, 2001. p. 509-518 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with host publication)peer-review