TY - JOUR
T1 - A class of algorithms which require nonlinear time to maintain disjoint sets
AU - Tarjan, Robert Endre
N1 - Funding Information:
* This research was supported in part by National Science Foundation grant MCS75-22870 by the Office of Naval Research contract NOOO14-76-C-0688. The United States Government’s right to retain a nonexclusive royalty-free license in and to copyright covering this paper is acknowledged.
PY - 1979/4
Y1 - 1979/4
N2 - 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 defines a class of algorithms which compute unions of disjoint sets on-line, and proves that any such algorithm requires nonlinear time in the worst case. All set union algorithms known to the author 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.
AB - 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 defines a class of algorithms which compute unions of disjoint sets on-line, and proves that any such algorithm requires nonlinear time in the worst case. All set union algorithms known to the author 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.
UR - http://www.scopus.com/inward/record.url?scp=0018455018&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0018455018&partnerID=8YFLogxK
U2 - 10.1016/0022-0000(79)90042-4
DO - 10.1016/0022-0000(79)90042-4
M3 - Article
AN - SCOPUS:0018455018
SN - 0022-0000
VL - 18
SP - 110
EP - 127
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -