Dynamic Maintenance of Majority Information in Constant Time per Update
DOI:
https://doi.org/10.7146/brics.v2i45.19946Abstract
We show how to maintain information about the existence of amajority 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.
Downloads
Published
1995-06-15
How to Cite
Frandsen, G. S., & Skyum, S. (1995). Dynamic Maintenance of Majority Information in Constant Time per Update. BRICS Report Series, 2(45). https://doi.org/10.7146/brics.v2i45.19946
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.