@article{ART001885812},
author={Inbum Kim and 김수인},
title={Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={6},
pages={71-80}
TY - JOUR
AU - Inbum Kim
AU - 김수인
TI - Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 6
PB - The Korean Society Of Computer And Information
SP - 71
EP - 80
SN - 1598-849X
AB - Employing PTAS to building minimum spanning tree for a large number of equal distributioninput terminal nodes can be a effective way in execution time. But applying PTAS to building minimum spanning tree for tremendous unequal distribution node may lead to performancedegradation. In this paper, a partial PTAS reflecting the scheme into specific node dense area ispresented. In the environment where 90% of 50,000 input terminal nodes stand close together inspecific area, approximate minimum spanning tree by our proposed scheme can show about 88.49%execution time less and 0.86%tree length less than by existing PTAS, and about 87.57%executiontime less and 1.18% tree length more than by Prim’s naive scheme. Therefore our scheme can gowell to many useful applications where a multitude of nodes gathered around specific area shouldbe connected efficiently as soon as possible.
KW - Polynomial-Time Approximation Scheme;Minimum Spanning Tree;Prim‘s Algorithm;Unequality Node Distribution
DO -
UR -
ER -
Inbum Kim and 김수인. (2014). Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution. Journal of The Korea Society of Computer and Information, 19(6), 71-80.
Inbum Kim and 김수인. 2014, "Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution", Journal of The Korea Society of Computer and Information, vol.19, no.6 pp.71-80.
Inbum Kim, 김수인 "Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution" Journal of The Korea Society of Computer and Information 19.6 pp.71-80 (2014) : 71.
Inbum Kim, 김수인. Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution. 2014; 19(6), 71-80.
Inbum Kim and 김수인. "Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution" Journal of The Korea Society of Computer and Information 19, no.6 (2014) : 71-80.
Inbum Kim; 김수인. Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution. Journal of The Korea Society of Computer and Information, 19(6), 71-80.
Inbum Kim; 김수인. Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution. Journal of The Korea Society of Computer and Information. 2014; 19(6) 71-80.
Inbum Kim, 김수인. Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution. 2014; 19(6), 71-80.
Inbum Kim and 김수인. "Efficient Construction of Euclidean Minimum Spanning Tree Using Partial Polynomial-Time Approximation Scheme in Unequality Node Distribution" Journal of The Korea Society of Computer and Information 19, no.6 (2014) : 71-80.
