Logo image
Back
Parallel algorithms for the tree bisector problem and applications
Conference paper

Parallel algorithms for the tree bisector problem and applications

Biing-Feng Wang, Shan-Chyun Ku, Keng-Hua Shi, Ting-Kai Hung and Pei-Sen Liu
IEEE Xplore Digital Library 1999 International Conference on Parallel Processing, p.192
1999
DOI: https://doi.org/10.1109/ICPP.1999.797404

Abstract

Parallel algorithms;Phase change random access memory;Application software;Computer science;Computer industry;Joining processes
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

Metrics

1 Record Views

Details

Logo image