Exact and Heuristic Algorithms for the Optimum Communication Spanning Tree Problem

R. K. Ahuja and V. V. S. Murty
Additional contact information
R. K. Ahuja: Indian Institute of Technology, Kanpur 208 016, India
V. V. S. Murty: OMC Computers Ltd., Secunderabad, India

Transportation Science, 1987, vol. 21, issue 3, 163-170

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.

Date: 1987
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.21.3.163 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:21:y:1987:i:3:p:163-170

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().