期刊名称：International Journal of Computer Science and Network Security
印刷版ISSN：1738-7906
出版年度：2006
卷号：6
期号：12
页码：60-72
出版社：International Journal of Computer Science and Network Security
摘要：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. Most researches on GOSST have concentrated on geometric analyses and approximation algorithms. Since all published solutions for optimization problems require tremendous computation and memory space, it might be hard to apply those to practical problems. Therefore GOSST, one of the optimization problems, could not escape the foible. In this research, a feasible heuristic for GOSST problems is proposed, implemented and analyzed. For more exquisite designed heuristic, more studies and trials are necessary.
关键词：GOSST, Steiner Point, Minimum Spanning Tree, Network Construction Cost, Global Connecting, Local Connecting G-condition
