To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
An Enhanced Heuristic Using Direct Steiner Point Locating and Distance Preferring MST Building Strategy for GOSST Problem |
|
Author |
Inbum Kim, Chae-kak Kim |
| Citation |
Vol. 7 No. 2 pp. 164-175 |
|
Abstract |
An enhanced heuristic for the GOSST (Grade of Services Steiner Minimum Tree) problem is proposed in this paper. GOSST problem is to look for a network topology satisfying the G-condition with minimum construction cost of the network. In previous research, we proposed a heuristic for the problem, which employed two Steiner point locating strategies with Na?ve MST (Minimum Spanning Tree) building strategy. The GOSST heuristic of this paper employs new Steiner point locating strategy and MST building strategy, which are Direct Locating strategy and Distance Preferring MST building strategy. Based on the results of this research, we can assert the Direct Steiner point Location strategy is better than Global or Local location strategy of our previous research, and the Distance Preferring MST building strategy is better than previous Na?ve MST building strategy. And the Distance Direct GOSST method employing the Distance Preferring MST building strategy and the Direct Steiner point Locating strategy entails the least network construction cost and acquires 13.2% enhancement by comparison to the Na?ve Global method, the best GOSST method in our previous research [19]. |
|
Keywords |
GOSST, Steiner Point, Minimum Spanning Tree, Network Construction Cost, Locating Strategy, MST building Strategy, Direct locating, Global Locating, Local Locating, Distance Preferring, G-condition, G-MST |
|
URL |
