Problem reduction methods and a tree generation algorithm for the steiner network problem
作者:
Anantaram Balakrishnan,
Nitin R. Patel,
期刊:
Networks
(WILEY Available online 1987)
卷期:
Volume 17,
issue 1
页码: 65-85
ISSN:0028-3045
年代: 1987
DOI:10.1002/net.3230170107
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThe Steiner network problem seeks a minimum weight connected subgraph that spans a specified subset off nodes in a given graph and optionally uses any of the other nodes as intermediate or Steiner points. This model has a variety of practical applications particularly in location, transportation, and communication planning. In this paper, we first outline some distinctive characteristics of optimal Steiner network solutions and propose a problem reduction procedure based on these properties. We derive a conservative estimate of the expected reduction achieved by this method under one set of probabilistic assumptions and demonstrate that this scheme produces asymptotically optimal reduction. We also report computational results for several randomly generated test problems. We then devise a tree generation algorithm that exploits the special structure of the Steiner network problem while solving its constrained minimal spanning tree formulation.
点击下载:
PDF
(1216KB)
返 回