Abstract
Let T=(V, E) be a free tree with vertex set V and edge set E. Let n=|V|. Each e□E has a non-negative length. In this thesis, we first present an algorithm on the CREW PRAM for solving the V/V/r-dominating set problem on T, where r□0 is a real number. The presented algorithm requires O(log^2 n) time using O(nlog n) work. Applying this algorithm as a procedure for testing feasibility, we then solve the V/V/p-center problem on the CREW PRAM in O(log^3 n) time using O(nlog^2 n) work, where p>1 is an integer. Previously, He and Yesha had proposed parallel algorithms on the CREW PRAM for special cases of the V/V/r-dominating set and the V/V/p-center problems, in which r is an integer and the lengths of all edges are 1. Their V/V/r-dominating set algorithm requires O(log nloglog n) time using O(nlog nloglog n) work; and their V/V/p-center algorithm requires O(log^2 nloglog n) time using O(nlog^2 nloglog n) work. As compared with He and Yesha's results, ours are more general and more efficient from the aspect of work. Key words: trees, r-dominating sets, p-centers, network location theory, parallel algorithms, CREW PRAM.