Steiner tree problem with minimum number of Steiner points and bounded edge-length

被引：223

作者：

Lin, GH

Xue, GL ^{[1
]}

机构：

[1] Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA

[2] Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 02期

基金：

美国国家科学基金会;

关键词：

algorithms; approximation algorithms; Steiner minimum trees; VLSI design; WDM optimal networks; wireless communications;

D O I：

10.1016/S0020-0190(98)00201-4

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STP-MSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：53 / 57

页数：5

共 11 条

[1] GLOBAL ROUTING BASED ON STEINER MIN-MAX TREES [J].