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