This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1987, with author Gaibisso C., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 206  (Previous ) 


Carlo Gaibisso

A partially persistent data structure for the set-union problem with backtracking.

ABSTRACT

An extension of the well known Set-Union problem is considered, where searching in the history of the partition and backtracking over the Union operations are possible. A partially persistent data structure is presented which maintains a partition of an n-item set and performs each Union, each Find and each search in the past in O(lg n) time per operation, at the same time allowing to backtrack over the sequence of Unions in constant time. The space complexity of such a structure is O(n).