@article{ART001846806},
author={Inbum Kim},
title={Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={1},
pages={57-64}
TY - JOUR
AU - Inbum Kim
TI - Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 1
PB - The Korean Society Of Computer And Information
SP - 57
EP - 64
SN - 1598-849X
AB - As Steiner minimum tree building belongs to NP-Complete problem domain, heuristics for theproblem ask for immense amount execution time and computations in numerous inputs. In thispaper, we propose an efficient mechanism of euclidean Steiner minimum tree construction fornumerous inputs using combination of Delaunay triangulation and Prim’s minimum spanning tree algorithm. Trees built by proposed mechanism are compared respectively with the Prim’s minimumspanning tree and minimums spanning tree based Steiner minimum tree. For 30,000 input nodes,Steiner minimum tree by proposed mechanism shows about 2.1% tree length less and 138.2%execution time more than minimum spanning tree, and does about 0.013% tree length less and18.9% execution time less than minimum spanning tree based Steiner minimum tree inexperimental results. Therefore the proposed mechanism can work moderately well to many usefulapplications where execution time is not critical but reduction of tree length is a key factor
KW - Delaunay Triangulation;Euclidean Steiner Minimum Tree;Minimum Spanning Tree;Tree Length
DO -
UR -
ER -
Inbum Kim. (2014). Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(1), 57-64.
Inbum Kim. 2014, "Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree", Journal of The Korea Society of Computer and Information, vol.19, no.1 pp.57-64.
Inbum Kim "Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19.1 pp.57-64 (2014) : 57.
Inbum Kim. Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree. 2014; 19(1), 57-64.
Inbum Kim. "Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.1 (2014) : 57-64.
Inbum Kim. Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(1), 57-64.
Inbum Kim. Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree. Journal of The Korea Society of Computer and Information. 2014; 19(1) 57-64.
Inbum Kim. Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree. 2014; 19(1), 57-64.
Inbum Kim. "Efficient Construction of Euclidean Steiner Minimum Tree Using Combination of Delaunay Triangulation and Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.1 (2014) : 57-64.
