Aarhus University Seal / Aarhus Universitets segl

Dynamic maintenance of majority information in constant time per update

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Department of Computer Science
  • Faculty of Science
We show how to maintain information about the existence of a majority colour in a set of elements under insertion and deletion of single elements using O(1) time and at most 4 equality tests on colours per update. No ordering information is used.
Original languageEnglish
JournalInformation Processing Letters
Volume63
Issue2
Pages (from-to)75-78
Number of pages4
ISSN0020-0190
DOIs
Publication statusPublished - 1997

See relations at Aarhus University Citationformats

ID: 36649404