An FPTAS for weight-constrained Steiner trees in series-parallel graphs

被引：0
|
作者：
Chen, GT [1 ]
Xue, GL
机构：
[1] Hongzhou Inst Elect Engn, Sch Sci & Arts, Hangzhou, Peoples R China
[2] Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA
来源：
COMPUTING AND COMBINATORICS | 2001年 / 2108卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we study the problem of computing a minimum cost Steiner tree subject to weight constraint in a series-parallel graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We present a fully polynomial time approximation scheme for this NP-complete problem.
引用
收藏
页码：519 / 528
页数：10
相关论文
共 50 条
12345