BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-603
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Reference machines require non-linear time to maintain
               disjoint sets
        TYPE:: Technical Report
      AUTHOR:: Tarjan, Robert Endre
        DATE:: March 1977
       PAGES:: 48
    ABSTRACT:: This paper describes a machine model intended to be useful in
               deriving realistic complexity bounds for tasks requiring list
               processing. As an example of the use of the model, the paper
               shows that any such machine requires non-linear time in the
               worst case to compute unions of disjoint sets on-line. All
               set union algorithms known to me are instances of the model
               and are thus subject to the derived bound. One of the known
               algorithms achieves the bound to within a constant factor.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-603