A Heuristic Using GOSST With 2 Connecting Strategies for Minimum Construction Cost of Network

The goal of this research is to devise a heuristic to solve the GOSST (Grade Of Services Steiner Minimum Tree) problem that could apply to the design of communication networks. GOSST problem is to find a network topology satisfying the G-condition with minimum construction cost. The proposed heuristic might provide a way to design of more economical network offering differential grade of services. The heuristic employs Minimum Spanning Tree, Steiner Point and two connection strategies. The implemented methods will be analyzed their performance and characteristics for examining the heuristic. Because GOSST problem is known to be NP-Complete, proposed heuristic to find a reasonable solution might have some limitation essentially.