BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-728
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Union-member algorithms for non-disjoint sets
        TYPE:: Technical Report
      AUTHOR:: Shiloach, Yossi
        DATE:: January 1979
       PAGES:: 13
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-728