Report Number: CS-TR-79-728
Institution: Stanford University, Department of Computer Science
Title: Union-member algorithms for non-disjoint sets
Author: Shiloach, Yossi
Date: January 1979
Abstract: In this paper we deal with the following problem. We are given a finite set U = {$u_1$,...,$u_n$} and a set [cursive capital 'S'] = {$S_1$,...,$S_m$} of subsets of U. We are also given m-1 UNION instructions that have the form UNION($S_i$,$S_j$) and mean "add the set $S_i \cup S_j$ to the collection and delete $S_i$ and $S_j$." Interspaced among the UNIONs are MEMBER(i,j) questions that mean "does $u_i$ belong to $S_j$?" We present two algorithms that exhibit the trade-off among the three interesting parameters of this problem, which are: 1. Time required to answer one membership question. 2. Time required to perform the m-1 UNIONs altogether. 3. Space. We also give an application of these algorithms to the problem of 5-coloring of planar graphs.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/728/CS-TR-79-728.pdf