Premium
Problem reduction methods and a tree generation algorithm for the steiner network problem
Author(s) -
Balakrishnan Anantaram,
Patel Nitin R.
Publication year - 1987
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230170107
Subject(s) - steiner tree problem , reduction (mathematics) , mathematics , spanning tree , mathematical optimization , probabilistic logic , tree (set theory) , computer science , algorithm , graph , minimum spanning tree , network planning and design , combinatorics , artificial intelligence , computer network , geometry
The 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.