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

Dingzhu Du; Lusheng Wang; Baogang Xu

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

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Overview

30 Scopus Citations

Scopus Metrics

View graph of relations

Author(s)

Dingzhu Du
Lusheng Wang
Baogang Xu

Related Research Unit(s)

Department of Computer Science

Detail(s)

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	7th Annual International Conference, COCOON 2001, Proceedings
Editors	Jie Wang
Publisher	Springer Verlag
Pages	509-518
Volume	2108
ISBN (print)	9783540424949
Publication status	Published - 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2108
ISSN (Print)	0302-9743
ISSN (electronic)	1611-3349

Conference

Title	7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Place	China
City	Guilin
Period	20 - 23 August 2001

Link(s)

	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-84944073631&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(8b9c8d9d-2a14-4c30-9b2a-c3dc0e165d87).html

Abstract

We study variations of Steiner tree problem. Let P = {p₁, p₂,…, p_n} 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(n³); (3) a ratio-5/2 approximation algorithm for STP-MSP.

Fingerprint

Publication fingerprints text

100

Steiner Point Mathematics

100

steiner tree Computer Science

Tree Problem Mathematics

Approximation Algor... Computer Science

Steiner Tree Proble... Computer Science

Edge Mathematics

Positive Integer Mathematics

Running Time Mathematics

Euclidean Plane Mathematics

Positive Constant Mathematics

Full Fingerprint ›

Citation Format(s)

[ RIS ] [ BibTeX ]

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 32 - Refereed conference paper (with host publication) › peer-review

Du, D, Wang, L & Xu, B 2001, The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. in J Wang (ed.), Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Proceedings. vol. 2108, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2108, Springer Verlag, pp. 509-518, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 20/08/01.

Du, D., Wang, L., & Xu, B. (2001). The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In J. Wang (Ed.), Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Proceedings (Vol. 2108, pp. 509-518). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108). Springer Verlag.

Du D, Wang L, Xu B. The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In Wang J, editor, Computing and Combinatorics: 7th Annual International Conference, COCOON 2001, Proceedings. 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)).

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