TIME-OPTIMAL ALGORITHMS FOR GENERALIZED DOMINANCE COMPUTATION AND RELATED PROBLEMS ON MESH CONNECTED COMPUTERS AND MESHES WITH MULTIPLE BROADCASTING
Titel:
TIME-OPTIMAL ALGORITHMS FOR GENERALIZED DOMINANCE COMPUTATION AND RELATED PROBLEMS ON MESH CONNECTED COMPUTERS AND MESHES WITH MULTIPLE BROADCASTING
Auteur:
Stoica, Ion
Verschenen in:
International journal of parallel, emergent and distributed systems
Paginering:
Jaargang 8 (1996) nr. 3-4 pagina's 271-283
Jaar:
1996
Inhoud:
The generalized dominance computation (GDC) problem is stated as follows: Let A = {a1, a2, …, an} be a set of triplets, i.e., ai = (xi, yi,fi), “⊲” be a linear order relation defined on x-components, “<” be a linear order relation defined on y-components, and “⊕” an abelian operator defined on f-components. It is required to compute for every ai ∈ A, the expression D(ai) = fj1 ⊕ fj2 ⊕ … ⊕ fjk, where { j1,j2, … jk { is the set of all indices j such that aj ∈ A and xj ⊲ xi, yj < yi. First, this paper presents a time-optimal algorithm to solve the GDC problem in O(√n ) on a mesh connected computer of size. √n × √n. To prove the generality of our approach, we show how a number of computational geometry problems, such as ECDF (empirical cumulative distribution function) searching and two-set dominance counting, can be derived from GDC problem. Second, we define a natural extension of the GDC, called mulliple-query generalized dominance computation (MQGDC), on meshes with multiple broadcasting. By using multiple querying (MQ) paradigm of Bokka et al. |3, 4, 6| we devise a time-optimal algorithm that solves a MQGDC problem involving a set A of n items and a set Q of m queries in O (n⅙ ⅓) on a mesh with multiple broadcasting of size √n × √n.
Tijdschrift beschrijving