Dynamic graph coloring

Luis Barba; Jean Cardinal; Matias Korman; Stefan Langerman; André van Renssen; Marcel Roeloffzen; Sander Verdonschot

doi:10.1007/978-3-319-62127-2_9

Dynamic graph coloring

Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, Sander Verdonschot

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

16 Citations (Scopus)

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(CdN^1/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(dN^1/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	https://doi.org/10.1007/978-3-319-62127-2_9
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	http://www.wads.org/

Access to Document

10.1007/978-3-319-62127-2_9

Cite this

Barba, L., Cardinal, J., Korman, M., Langerman, S., van Renssen, A., Roeloffzen, M., & Verdonschot, S. (2017). Dynamic graph coloring. In E. Faith, A. Kolokolova, & J-R. Sack (Eds.), Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings (pp. 97-108). (Lecture Notes in Computer Science; Vol. 10389). Springer. https://doi.org/10.1007/978-3-319-62127-2_9

@inproceedings{5e33d0d5d2044bcca543990bddf3e3fb,

title = "Dynamic graph coloring",

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.",

author = "Luis Barba and Jean Cardinal and Matias Korman and Stefan Langerman and {van Renssen}, Andr{\'e} and Marcel Roeloffzen and Sander Verdonschot",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-62127-2_9",

language = "English",

isbn = "9783319621265",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "97--108",

editor = "E. Faith and A. Kolokolova and J.-R. Sack",

booktitle = "Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings",

address = "Germany",

note = "15th International Symposium on Algorithms and Data Structures (WADS 2017), WADS 2017 ; Conference date: 31-07-2017 Through 02-08-2017",

url = "http://www.wads.org/",

}

Barba, L, Cardinal, J, Korman, M, Langerman, S, van Renssen, A, Roeloffzen, M & Verdonschot, S 2017, Dynamic graph coloring. in E Faith, A Kolokolova & J-R Sack (eds), Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings . Lecture Notes in Computer Science, vol. 10389, Springer, Berlin, pp. 97-108, 15th International Symposium on Algorithms and Data Structures (WADS 2017), St. John’s, Newfoundland and Labrador, Canada, 31/07/17. https://doi.org/10.1007/978-3-319-62127-2_9

Dynamic graph coloring. / Barba, Luis; Cardinal, Jean; Korman, Matias et al.

Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings . ed. / E. Faith; A. Kolokolova; J.-R. Sack. Berlin : Springer, 2017. p. 97-108 (Lecture Notes in Computer Science; Vol. 10389).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Dynamic graph coloring

AU - Barba, Luis

AU - Cardinal, Jean

AU - Korman, Matias

AU - Langerman, Stefan

AU - van Renssen, André

AU - Roeloffzen, Marcel

AU - Verdonschot, Sander

N1 - Conference code: 15

PY - 2017/1/1

Y1 - 2017/1/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85024370811&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62127-2_9

DO - 10.1007/978-3-319-62127-2_9

M3 - Conference contribution

AN - SCOPUS:85024370811

SN - 9783319621265

T3 - Lecture Notes in Computer Science

SP - 97

EP - 108

BT - Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings

A2 - Faith, E.

A2 - Kolokolova, A.

A2 - Sack, J.-R.

PB - Springer

CY - Berlin

T2 - 15th International Symposium on Algorithms and Data Structures (WADS 2017)

Y2 - 31 July 2017 through 2 August 2017

ER -

Barba L, Cardinal J, Korman M, Langerman S, van Renssen A, Roeloffzen M et al. Dynamic graph coloring. In Faith E, Kolokolova A, Sack J-R, editors, Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL Canada, July 31- August 2, 2017, Proceedings . Berlin: Springer. 2017. p. 97-108. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-319-62127-2_9

Dynamic graph coloring

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this