A Proposal of Heuristic Using Zigzag Steiner Point Locating Strategy for GOSST Problem


The KIPS Transactions:PartA, Vol. 14, No. 5, pp. 317-326, Oct. 2007
10.3745/KIPSTA.2007.14.5.317,   PDF Download:

Abstract

We propose more enhanced heuristic for the GOSST (Grade of Services Steiner Minimum Tree) problem in this paper. GOSST problem is a variation of Steiner Tree problem and to find a network topology satisfying the G-Condition with minimum network construction cost.GOSST problem is known as one of NP-Hard or NP-Complete problems. In previous our research, we proposed a heuristic employing Direct Steiner point Locating strategy with Distance Preferring MST building strategy. In this paper, we propose new Steiner point locating strategy, Zigzag Steiner point Locating strategy. Through the results of out experiments, we can assert this strategy is better than our previous works. The Distance Zigzag GOSST method which hires the Distance Preferring MST building strategy and Zigzag Steiner point Locating strategy defrays the least network construction cost and brings 31.5% cost saving by comparison to G-MST, the experimental control and 2.2% enhancement by comparison to the Distance Direct GOSST method, the best GOSST method in our previous research.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
I. B. Kim and C. K. Kim, "A Proposal of Heuristic Using Zigzag Steiner Point Locating Strategy for GOSST Problem," The KIPS Transactions:PartA, vol. 14, no. 5, pp. 317-326, 2007. DOI: 10.3745/KIPSTA.2007.14.5.317.

[ACM Style]
In Bum Kim and Chae Kak Kim. 2007. A Proposal of Heuristic Using Zigzag Steiner Point Locating Strategy for GOSST Problem. The KIPS Transactions:PartA, 14, 5, (2007), 317-326. DOI: 10.3745/KIPSTA.2007.14.5.317.