The node‐weighted steiner tree problem
作者:
Arie Segev,
期刊:
Networks
(WILEY Available online 1987)
卷期:
Volume 17,
issue 1
页码: 1-17
ISSN:0028-3045
年代: 1987
DOI:10.1002/net.3230170102
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThe general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experi
点击下载:
PDF
(745KB)
返 回