Constrained Steiner trees in Halin graphs

被引:24
作者
Chen, GT
Burkard, RE
机构
[1] Hangzhou Inst Elect Engn, Sch Sci, Hangzhou 310037, Peoples R China
[2] Graz Univ Technol, Inst Math, A-8010 Graz, Austria
关键词
Steiner trees; Halin graph; approximation scheme;
D O I
10.1051/ro:2003020
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.
引用
收藏
页码:179 / 193
页数:15
相关论文
共 10 条
[1]  
Chen GT, 2001, LECT NOTES COMPUT SC, V2108, P519
[2]  
Chen GT, 2001, SIAM PROC S, P230
[3]   APPROXIMATION SCHEMES FOR THE RESTRICTED SHORTEST-PATH PROBLEM [J].
HASSIN, R .
MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (01) :36-42
[4]  
HWANBG FK, 1992, ANN DISCRETE MATH, V53, P68
[5]   STEINER TREE PROBLEMS [J].
HWANG, FK ;
RICHARDS, DS .
NETWORKS, 1992, 22 (01) :55-89
[6]  
Jiang T, 2000, COMB OPT (SER), V6, P39
[7]  
Johnson, 1979, COMPUTERS INTRACTABI, V174
[8]   A simple efficient approximation scheme for the restricted shortest path problem [J].
Lorenz, DH ;
Raz, D .
OPERATIONS RESEARCH LETTERS, 2001, 28 (05) :213-219
[9]   STEINER PROBLEM IN NETWORKS - A SURVEY [J].
WINTER, P .
NETWORKS, 1987, 17 (02) :129-167
[10]   STEINER PROBLEM IN HALIN NETWORKS [J].
WINTER, P .
DISCRETE APPLIED MATHEMATICS, 1987, 17 (03) :281-294