Name
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(\mathcal {C} dN ^{1/d})\)-coloring while recoloring at most O(d) vertices per update, where \(\mathcal {C} \) and \(N \) are the maximum chromatic number and maximum number of vertices, respectively. The second algorithm reverses the trade-off, maintaining an \(O(\mathcal {C} d)\)-coloring with \(O(dN ^{1/d})\) recolorings per update. The two converge when \(d = \log N \), maintaining an \(O(\mathcal {C} \log N)\)-coloring with \(O(\log N)\) 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 \(\varOmega (N ^\frac{2}{c(c-1)})\) vertices per update, for any constant \(c \ge 2\). |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00453-018-0473-y | WADS |
Keywords | DocType | Volume |
Dynamic coloring,Graphs,Data structures,Amortized algorithms | Journal | abs/1708.09080 |
Issue | ISSN | Citations |
4 | 0178-4617 | 1 |
PageRank | References | Authors |
0.63 | 6 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luis Barba | 1 | 83 | 15.38 |
| Jean Cardinal | 2 | 335 | 47.57 |
| Matias Korman | 3 | 178 | 37.28 |
| Stefan Langerman | 4 | 831 | 101.66 |
| André van Renssen | 5 | 3 | 4.74 |
| Marcel Roeloffzen | 6 | 1 | 0.63 |
| Sander Verdonschot | 7 | 110 | 17.98 |