Finding r-dominating sets and p-centers of trees in parallel

Let T=(V, E) be an edge-weighted tree with |V|=n vertices embedded in the Euclidean plane. Let IE denote the set of all points on the edges of T. Let X and Y be two subsets of IE and let r be a positive real number. A subset D⊆X is an X/Y/r-dominating set if every point in Y is within distance r of a point in D. The X/Y/r-dominating set problem is to find an X/Y/r-dominating set D* with minimum cardinality. Let p≥1 be an integer. The X/Y/p-center problem is to find a subset C*⊆X of p points such that the maximum distance of any point in Y from C* is minimized. Let X and Y be either V or IE. In this paper, efficient parallel algorithms on the EREW PRAM are first presented for the X/Y/r-dominating set problem. The presented algorithms require O(log²n) time for all cases of X and Y. Parallel algorithms on the EREW PRAM are then developed for the X/Y/p-center problem. The presented algorithms require O(log³n) time for all cases of X and Y. Previously, sequential algorithms for these two problems had been extensively studied in the literature. However, parallel solutions with polylogarithmic time existed only for their special cases. The algorithms presented in this paper are obtained by using an interesting approach which we call the dependency-tree approach. Our results are examples of parallelizing sequential dynamic-programming algorithms by using the approach.