A Study on the Choice of G-Node and Disconnection to Improve the Heuristic for the GOSST Problem

This paper deals with the enhancement of the heuristic for the grade of service Steiner minimum tree problem that could be applied to the design of communication networks offering graduated services. This problem, which is known as one of the NP-hard problems, attempts to find a network with the minimum construction cost meeting the G-condition. In prior research, we proposed a heuristic based on the local Steiner point locating policy in conjunction with the distance preferring minimum spanning tree building policy. Herein, we suggest methods of selecting the G-node and disconnections for the distance local GOSST heuristic for the problem in this paper. The ameliorated heuristic provides a 17% improvement in the network construction cost saving ratio to G-MST.