Efficient parallel algorithms for r-dominating set and p-center problems on trees (Q1262780): Difference between revisions

Let \(T=(V,E)\) be a tree with \(| V| =n\) vertices embedded in the Euclidean plane with straight edges, and let A be the set of all points of T. For any x, y in A, d(x,y) is the distance, measured along the edges of T, between x and y. Given any subsets X, Y of A, the X/Y/r-dominating set problem is to find a minimum-cardinality subset \(D^*\) of X such that for every point y of Y there is some point x in X within distance r of y, and the X/Y/p-centre problem is to find a p-element subset \(C^*\) of X which minimizes the maximum distance from any point in Y to the closest point in \(C^*.\) Linear-time sequential algorithms for the V/V/r- and A/V/r-dominating set problems are given in [\textit{O. Kariv} and \textit{S. L. Hakimi}, SIAM J. Appl. Math. 37, 513-538 (1979; Zbl 0432.90074)], and for V/A/r- and A/A/r-dominating set problems in [\textit{R. Chandrasekaran} and \textit{A. Tamir}, SIAM J. Algebraic Discrete Methods 1, 370-375 (1980; Zbl 0496.68045)]. A parallel algorithm for the V/V/r-dominating set problem, which takes O(log n) time with rn processors, is given in [\textit{X. He} and \textit{Y. Yesha}, J. Algorithms 9, No.1, 92-113 (1988; Zbl 0647.68067)]. The present paper solves it in O(log n log log n) time with n processors on a CREW PRAM, provided that r is an integer and all edges have lengths 1, and extensions to the V/A, A/V and A/A problems are suggested. Sequential algorithms for the four p-center problems which run in O(pn log(n/p)) for the A/A problem and O(n log n) for the other three are given in [\textit{G.-N. Frederickson} and \textit{D. B. Johnson}, J. Algorithms 4, 61-80 (1983; Zbl 0509.68057)]. The present paper parallelizes them to run in \(O(\log^ 2n \log \log n)\) time using pn processors for the A/A problem and n processors for the other three, provided that all edges have length 1.