KJCKorea
Journal Central

@article{ART001683590},
author={Inbum Kim},
title={Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2012},
volume={17},
number={7},
pages={87-95},
doi={}

TY - JOUR
AU - Inbum Kim
TI - Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS
JO - Journal of The Korea Society of Computer and Information
PY - 2012
VL - 17
IS - 7
PB - The Korean Society Of Computer And Information
SP - 87
EP - 95
SN - 1598-849X
AB - In this paper, PTAS three-dimensional Steiner minimum tree connecting numerous input nodes rapidly in 3D space is proposed. Steiner minimum tree problem belongs to NP problem domain, and when properly devised heuristic introduces, it is generally superior to other algorithms as minimum spanning tree affiliated with P problem domain. But when the number of input nodes is very large, the problem requires excessive execution time. In this paper, a method using PTAS is proposed to solve the difficulty. In experiments for 70,000 input nodes in 3D space, the tree produced by the proposed 8 space partitioned PTAS method reduced 86.88% execution time, compared with the tree by naive 3D steiner minimum tree method, though increased 0.81% tree length. This affirms the proposed method can work well for applications that many nodes of three dimensions are need to connect swifty, enduring slight increase of tree length.
KW - PTAS;Steiner Minimum Tree;Minimum Spanning Tree;3-Dimensional Space;Execution Time
DO -
ER -

Inbum Kim. (2012). Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS. Journal of The Korea Society of Computer and Information, 17(7), 87-95.

Inbum Kim. 2012, "Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS", Journal of The Korea Society of Computer and Information, vol.17, no.7 pp.87-95. Available from: doi:

Inbum Kim "Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS" Journal of The Korea Society of Computer and Information 17.7 pp.87-95 (2012) : 87.

Inbum Kim. Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS. 2012; 17(7), 87-95. Available from: doi:

Inbum Kim. "Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS" Journal of The Korea Society of Computer and Information 17, no.7 (2012) : 87-95.doi:

Inbum Kim. Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS. Journal of The Korea Society of Computer and Information, 17(7), 87-95. doi:

Inbum Kim. Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS. Journal of The Korea Society of Computer and Information. 2012; 17(7) 87-95. doi:

Inbum Kim. Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS. 2012; 17(7), 87-95. Available from: doi:

Inbum Kim. "Fast Construction of Three Dimensional Steiner Minimum Tree Using PTAS" Journal of The Korea Society of Computer and Information 17, no.7 (2012) : 87-95.doi: