본문 바로가기
  • Home

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
  • Abbr : JKSCI
  • 2014, 19(1), pp.57-64
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Inbum Kim 1

1김포대학교

Accredited

ABSTRACT

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

Citation status

* References for papers published after 2022 are currently being built.