본문 바로가기
  • Home

Efficient Construction of Large Scale Grade of Services Steiner Tree Using Space Locality and Polynomial-Time Approximation Scheme

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2011, 16(11), pp.153-162
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

김인범 1

1김포대학

Accredited

ABSTRACT

As the problem of GOSST building belongs to NP compete domain, heuristics for the problem ask for immense amount execution time and computations in large scale inputs. In this paper, we propose an efficient mechanism for GOSST construction using space locality PTAS. For 40,000 input nodes with maximum weight 100, the proposed space locality PTAS GOSST with 16 unit areas can reduce about 4.00% of connection cost and 89.26% of execution time less than weighted minimum spanning tree method. Though the proposed method increases 0.03% of connection cost more, but cuts down 96.39% of execution time less than approximate GOSST method (SGOSST) without PTAS. Therefore the proposed space locality PTAS GOSST mechanism can work moderately well to many useful applications where a greate number of weighted inputs should be connected in short time with approximate minimum connection cost.

Citation status

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