Abstract
In this paper we study the number of vertex recolorings that an algorithm needs to perform in order to maintain a proper coloring of a graph under insertion and deletion of vertices and edges. We present two algorithms that achieve different trade-offs between the number of recolorings and the number of colors used. For any d > 0, the first algorithm maintains a proper O(CdN1/d)-coloring while recoloring at most O(d) vertices per update, where C and N are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an O(Cd)-coloring with O(dN1/d) recolorings per update. We also present a lower bound, showing that any algorithm that maintains a c-coloring of a 2-colorable graph on N vertices must recolor at least Ω(N 2/ c(c−1)) vertices per update, for any constant c ≥ 2.
Original language | English |
---|---|
Title of host publication | Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings |
Editors | E. Faith, A. Kolokolova, J.-R. Sack |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 97-108 |
Number of pages | 12 |
ISBN (Electronic) | 9783319621272 |
ISBN (Print) | 9783319621265 |
DOIs | |
Publication status | Published - 1 Jan 2017 |
Externally published | Yes |
Event | 15th International Symposium on Algorithms and Data Structures (WADS 2017) - Memorial University of Newfoundland, St. John’s, Canada Duration: 31 Jul 2017 → 2 Aug 2017 Conference number: 15 http://www.wads.org/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 10389 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 15th International Symposium on Algorithms and Data Structures (WADS 2017) |
---|---|
Abbreviated title | WADS 2017 |
Country/Territory | Canada |
City | St. John’s |
Period | 31/07/17 → 2/08/17 |
Internet address |