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. |

Abstract (English) |
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 EREW-PRAM Restore |

1) Download Document PDF |

Open access Restricted Private