A class of algorithms which require nonlinear time to maintain disjoint sets

Robert Endre Tarjan

doi:10.1016/0022-0000(79)90042-4

A class of algorithms which require nonlinear time to maintain disjoint sets

Robert Endre Tarjan

Research output: Contribution to journal › Article › peer-review

220 Scopus citations

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 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.

Original language	English (US)
Pages (from-to)	110-127
Number of pages	18
Journal	Journal of Computer and System Sciences
Volume	18
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(79)90042-4
State	Published - Apr 1979
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science
Applied Mathematics
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1016/0022-0000(79)90042-4

Cite this

@article{1f46818d3dc3451781454c23b07b8fe4,

title = "A class of algorithms which require nonlinear time to maintain disjoint sets",

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 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.",

author = "Tarjan, \{Robert Endre\}",

note = "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{\textquoteright}s right to retain a nonexclusive royalty-free license in and to copyright covering this paper is acknowledged.",

year = "1979",

month = apr,

doi = "10.1016/0022-0000(79)90042-4",

language = "English (US)",

volume = "18",

pages = "110--127",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

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 - https://www.scopus.com/pages/publications/0018455018

UR - https://www.scopus.com/pages/publications/0018455018#tab=citedBy

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 -

A class of algorithms which require nonlinear time to maintain disjoint sets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this