Title :
A Study on the Choice of G-Node and Disconnection to Improve the Heuristic for the GOSST Problem
Author :
Inbum Kim ; Hosseini, Seyed Hossein
Author_Institution :
Wisconsin-Milwaukee Univ., Milwaukee
Abstract :
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.
Keywords :
quality of service; telecommunication network topology; trees (mathematics); G-condition; G-node; GOSST problem; NP-hard problems; communication networks design; disconnections; distance local GOSST heuristic; grade-of-service Steiner minimum tree problem; graduated services; heuristic enhancement; local Steiner point locating policy; minimum spanning tree building policy; Buildings; Communication networks; Communications Society; Computer displays; Computer science; Costs; Joining processes; NP-hard problem; Peer to peer computing; Steiner trees;
Conference_Titel :
Consumer Communications and Networking Conference, 2008. CCNC 2008. 5th IEEE
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-1456-7
Electronic_ISBN :
978-1-4244-1457-4
DOI :
10.1109/ccnc08.2007.68