Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem

Publisher Website
Google Scholar
Abstract
Network design problems have been widely investigated in the literature. In this paper, we study one such design problem, known as the Optimum Communication Spanning Tree (OCST) problem. We develop an exact algorithm based on the branch and bound approach and a heuristic algorithm to solve the problem. The branch and bound algorithm uses the lower planes recently developed by the authors. Reoptimization of subproblems is extensively used to reduce computation. The heuristic algorithm is a two-phase algorithm: tree-building algorithm and tree-improvement algorithm. These algorithms have been tested on randomly generated Euclidean and non-Euclidean problems and results of these investigations are described. The branch and bound algorithm is able to solve moderately large sized problems in reasonable time. The two-phase heuristic algorithm has produced excellent results by providing optimal solutions for all the problems tested. Further, it is capable of solving problems of size 100 nodes and 1,000 arcs in about 30 seconds on DEC 10.

This publication has 0 references indexed in Scilit: