Let T=(V, E) be a tree with vertex set V and edge set E. Let n=|V|. Each e∈E has a non-negative length. In this paper, 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 algorithm requires O(log{sup}2 n) time using O(nlog n) work. Applying this algorithm as a procedure for testing feasibility, the V/V/p-center problem on the CREW PRAM is solved in O(log{sup}3 n) time using O(log{sup}2 n) work, where p≥1 is an integer. Previously, He and Yesha had proposed 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{sup}2 nloglog n) time using O(nlog{sup}2 nloglog n) work. As compared with He and Yesha's results, ours are more general and more efficient form the aspect of work.
展开▼
机译：令T =（V，E）是具有顶点集V和边缘组E.设N =树| V |。每个e∈E具有非负长度。在本文中，我们首先提出对乘员PRAM的算法用于在T，其中r≥0是实数求解V / V / R-支配集问题。该算法需要使用O（n日志n）的工作O（日志{SUP} 2 n）的时间。应用该算法作为过程用于测试可行性，对乘员PRAM的V / V / P-中心问题为O（log {SUP} 3 N），使用O时间（日志{SUP} 2 n）的工作，其中，P是解决≥1是一个整数。对乘员PRAM为V / V / R-支配集和V / V /对 - 中心问题的特殊情况下，其中r是一个整数和所有边缘的长度之前，他和耶沙提议的算法是1 ，其V / V / R-支配集算法需要O使用（日志nloglog n）的时间为O（n日志nloglog n）的工作;和它们的V / V /对 - 中心算法需要使用O（n日志{SUP} 2 nloglog n）的工作O（日志{SUP} 2 nloglog n）的时间。至于他和耶沙的结果相比较，我们的范围更加广泛，工作更有效率的方面。
展开▼
