Istituto di Scienza e Tecnologie dell'Informazione     
Pinotti M. C., Crupi V., Das S. A parallel solution to the extended set union problem with unlimited backtracking. In: 10th International Parallel Processing Symposium (Honolulu, Hawaii, 15-19 aprile 1996). Proceedings, pp. 182 - 186. IEEE, 1996.
We study on the EREW-PRAM model a parallel solution to the extended set union problem with unlimited backtracking which maintains a dynamic partition /spl Pi/ of an n-element set S subject to the usual operations Find, Union, Backtrack and Restore as well as the new operations SetUnion, MultiUnion. The SetUnion operation as a special case of the commonly known Union operation aimed to unify two pre-specified set-names, while MultiUnion operation deals with a batch of Union operations. A new data structure, called k-Parallel Union Find (or, k-PUF) trees, is introduced to represent a disjoint set in /spl Pi/. The structure is defined for a wide range for the parameter k, but the more interesting results are achieved for k=log n/log log n. In this case, using the k-PUF trees, both SetUnion and Restore operations are performed in constant parallel time requiring optimal work O(k). This constant-time performance is not achievable parallelizing the existing data structures. Moreover, using p=O(k) processors, MultiUnion for a batch of p operations is performed in O(k) time, requiring optimal work O(pk).
DOI: 10.1109/IPPS.1996.508055
Subject Backtrack

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional