본문 바로가기
  • Home

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

Inbum Kim 1 김수인 1

1김포대학교

Accredited

ABSTRACT

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.

Citation status

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