• DocumentCode
    3219527
  • Title

    Parallel algorithms for the tree bisector problem and applications

  • Author

    Wang, Biing-Feng ; Ku, Shan-Chyun ; Shi, Keng-Hua ; Hung, Ting-Kai ; Liu, Pei-Sen

  • Author_Institution
    Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
  • fYear
    1999
  • fDate
    1999
  • Firstpage
    192
  • Lastpage
    199
  • Abstract
    An edge is a bisector of a simple path if it contains the middle point of the path. In this paper, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and the other uses O(nlog n) work. The one using O(n) work is more efficient but only applicable to unweighted trees. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n2) work
  • Keywords
    computational complexity; computational geometry; concurrency theory; parallel algorithms; EREW PRAM; parallel algorithms; single-source algorithms; tree bisector problem; Application software; Computer industry; Computer science; Joining processes; Parallel algorithms; Phase change random access memory;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing, 1999. Proceedings. 1999 International Conference on
  • Conference_Location
    Aizu-Wakamatsu City
  • ISSN
    0190-3918
  • Print_ISBN
    0-7695-0350-0
  • Type

    conf

  • DOI
    10.1109/ICPP.1999.797404
  • Filename
    797404
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3219527