Dynamic maintenance of majority information in constant time per update

Gudmund Skovbjerg Frandsen; Sven Skyum

doi:10.1016/S0020-0190(97)00100-2

Dynamic maintenance of majority information in constant time per update

Gudmund Skovbjerg Frandsen, Sven Skyum

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

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 elements using O(1) time and at most 4 equality tests on colours per update. No ordering information is used.

Original language	English
Journal	Information Processing Letters
Volume	63
Issue	2
Pages (from-to)	75-78
Number of pages	4
ISSN	0020-0190
DOIs	https://doi.org/10.1016/S0020-0190(97)00100-2
Publication status	Published - 1997

Access to Document

10.1016/S0020-0190(97)00100-2

Cite this

@article{5f45540e333b4648af15291815406722,

title = "Dynamic maintenance of majority information in constant time per update",

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 elements using O(1) time and at most 4 equality tests on colours per update. No ordering information is used.",

author = "Frandsen, {Gudmund Skovbjerg} and Sven Skyum",

year = "1997",

doi = "10.1016/S0020-0190(97)00100-2",

language = "English",

volume = "63",

pages = "75--78",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier BV",

number = "2",

}

TY - JOUR

T1 - Dynamic maintenance of majority information in constant time per update

AU - Frandsen, Gudmund Skovbjerg

AU - Skyum, Sven

PY - 1997

Y1 - 1997

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

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

U2 - 10.1016/S0020-0190(97)00100-2

DO - 10.1016/S0020-0190(97)00100-2

M3 - Journal article

SN - 0020-0190

VL - 63

SP - 75

EP - 78

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2

ER -

Dynamic maintenance of majority information in constant time per update

Abstract

Access to Document

Fingerprint

Cite this