| A Steiner tree connects a designated set of “terminal” nodes in a graph. Steiner trees can model shared channels used in group communication, video conferencing or multicasting. An optimum Steiner tree connects its terminal members with a set of edges whose total weight is minimum. Various practical algorithms to this NP-complete problem have been proposed, including the well-known KMB algorithm which produces near-optimum results.; In this research, we propose an alternative algorithm, called the Shrubbery algorithm, that quickly constructs a good Steiner tree. Further, we present two optimization algorithms to minimize the tree cost. The insertion algorithm minimizes tree cost by implementing local neighborhood search to discover potential paths for replacement; and the deletion algorithm attempts to change the topology of current tree by removing selected paths and reconnects the tree. Both insertion and deletion algorithms can trade off running time and quality of solution.; We evaluate the performance of the proposed algorithms by running simulations with a large number of standard benchmarks. Our results show that, among all the data sets, the Shrubbery algorithm is much faster than the KMB algorithm, and by applying the insertion and deletion algorithms, can produce results of better quality. The Shrubbery algorithm can be implemented as a distributed protocol, allowing a Steiner multicast tree to adapt to a dynamically changing network conditions of adding and deleting nodes from the communication group for each multicast session. This application area will be described. |
