DYNAMIC MAINTENANCE OF MAJORITY INFORMATION IN CONSTANT-TIME PER UPDATE

Authors
FRANDSEN GS SKYUM S
Citation
Gs. Frandsen et S. Skyum, DYNAMIC MAINTENANCE OF MAJORITY INFORMATION IN CONSTANT-TIME PER UPDATE, Information processing letters, 63(2), 1997, pp. 75-78
Citations number
2
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
63
Issue
2
Year of publication
1997
Pages
75 - 78
Database
ISI
SICI code
0020-0190(1997)63:2<75:DMOMII>2.0.ZU;2-7
Abstract
We show how to maintain information about the existence of a majority colour in a set of elements under insertion and deletion of single ele ments using O(1) time and at most 4 equality tests on colours per upda te, No ordering information is used. (C) 1997 Elsevier Science B.V.