Dynamic Graph Coloring
| Autor: | Stefan Langerman, André van Renssen, Luis Barba, Marcel Roeloffzen, Jean Cardinal, Matias Korman, Sander Verdonschot |
|---|---|
| Přispěvatelé: | Algorithms, Geometry and Applications |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Data structures General Computer Science ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Combinatorics Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Dynamic coloring Graphs Amortized algorithms Théorie des graphes Data Structures and Algorithms (cs.DS) Graph coloring Physics Informatique générale Applied Mathematics Graph Théorie des algorithmes Computer Science Applications Vertex (geometry) 010201 computation theory & mathematics 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Algorithmica, 81 (4) Algorithmica Algorithmica, 81(4), 1319-1341. Springer |
| ISSN: | 0178-4617 1432-0541 |
| Popis: | 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. The two converge when d=logN, maintaining an O(ClogN)-coloring with O(logN) 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 Ω(N2c(c−1)) vertices per update, for any constant c≥2. Algorithmica, 81 (4) ISSN:0178-4617 ISSN:1432-0541 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink