KJCKorea
Journal Central

@article{ART001602862},
author={김인범},
title={Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2011},
volume={16},
number={11},
pages={153-162}

TY - JOUR
AU - 김인범
TI - Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme
JO - Journal of The Korea Society of Computer and Information
PY - 2011
VL - 16
IS - 11
PB - The Korean Society Of Computer And Information
SP - 153
EP - 162
SN - 1598-849X
AB - As the problem of GOSST building belongs to NP compete domain, heuristics for the problem ask for immense amount execution time and computations in large scale inputs. In this paper, we propose an efficient mechanism for GOSST construction using space locality PTAS. For 40,000 input nodes with maximum weight 100, the proposed space locality PTAS GOSST with 16 unit areas can reduce about 4.00% of connection cost and 89.26% of execution time less than weighted minimum spanning tree method. Though the proposed method increases 0.03% of connection cost more, but cuts down 96.39% of execution time less than approximate GOSST method (SGOSST) without PTAS. Therefore the proposed space locality PTAS GOSST mechanism can work moderately well to many useful applications where a greate number of weighted inputs should be connected in short time with approximate minimum connection cost.
KW - PTAS(Polynomial-Time Approximation Scheme);Minimum Spanning Tree;GOSST(Grade of Services Steiner Minimum Tree);Weight;Portal
DO -
UR -
ER -

김인범. (2011). Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme. Journal of The Korea Society of Computer and Information, 16(11), 153-162.

김인범. 2011, "Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme", Journal of The Korea Society of Computer and Information, vol.16, no.11 pp.153-162.

김인범 "Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme" Journal of The Korea Society of Computer and Information 16.11 pp.153-162 (2011) : 153.

김인범. Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme. 2011; 16(11), 153-162.

김인범. "Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme" Journal of The Korea Society of Computer and Information 16, no.11 (2011) : 153-162.

김인범. Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme. Journal of The Korea Society of Computer and Information, 16(11), 153-162.

김인범. Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme. Journal of The Korea Society of Computer and Information. 2011; 16(11) 153-162.

김인범. Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme. 2011; 16(11), 153-162.

김인범. "Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme" Journal of The Korea Society of Computer and Information 16, no.11 (2011) : 153-162.