论文标题
具有有界树木的图形的显式和隐式动态着色
Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity
论文作者
论文摘要
图形是计算机科学中的一个基本问题。我们研究了图形正在插入边缘插入和删除的问题的完全动态版本，我们希望在每次插入和删除后保持一个顶点颜色，并具有较小的更新时间。 我们展示了如何维护$ o（α\ lg n）$ - 使用Polygarithmic更新时间颜色，其中$ n $是图中的顶点数量，$α$是该图的当前支流。这取决于所罗门和Wein（Esa'18）的结果，他们维持$ O（α_ {\ max} \ lg^2 n）$ - 着色，其中$α_ {\ max max} $是所有更新中图的最大支流。 此外，由Barba等人的下限动机。 （Algorithmica'19），我们启动了隐式动态色素的研究。 Barba等。结果表明，具有polyogarithmic更新时间的动态算法无法维持$ f（α）$ - 在明确存储顶点颜色时，即任何功能$ f $的颜色，即每个顶点的颜色都明确存储在内存中。以前，所有动态算法都保持了明确的着色。因此，我们建议研究隐式着色，即，数据结构只需要提供有效的查询过程即可返回顶点的颜色（而不是明确地存储其颜色）。我们提供了一种算法，该算法破坏了下限并保持隐式$ 2^{o（α）} $ - 带有polygarithmic更新时间的颜色。特别是，这产生了第一个动态$ o（1）$ - 用于具有恒定树状图的图形的颜色，例如平面图或具有有界树宽的图形，使用显式颜色是不可能的。 我们还展示了如何在Polyogarithmic更新时间内动态地将图表边缘的分区划分为$ O（α）$ sorests。我们认为，这种数据结构具有独立的兴趣，将来可能会有更多的应用程序。
Graph coloring is a fundamental problem in computer science. We study the fully dynamic version of the problem in which the graph is undergoing edge insertions and deletions and we wish to maintain a vertex-coloring with small update time after each insertion and deletion. We show how to maintain an $O(α\lg n)$-coloring with polylogarithmic update time, where $n$ is the number of vertices in the graph and $α$ is the current arboricity of the graph. This improves upon a result by Solomon and Wein (ESA'18) who maintained an $O(α_{\max}\lg^2 n)$-coloring, where $α_{\max}$ is the maximum arboricity of the graph over all updates. Furthermore, motivated by a lower bound by Barba et al. (Algorithmica'19), we initiate the study of implicit dynamic colorings. Barba et al. showed that dynamic algorithms with polylogarithmic update time cannot maintain an $f(α)$-coloring for any function $f$ when the vertex colors are stored explicitly, i.e., for each vertex the color is stored explicitly in the memory. Previously, all dynamic algorithms maintained explicit colorings. Therefore, we propose to study implicit colorings, i.e., the data structure only needs to offer an efficient query procedure to return the color of a vertex (instead of storing its color explicitly). We provide an algorithm which breaks the lower bound and maintains an implicit $2^{O(α)}$-coloring with polylogarithmic update time. In particular, this yields the first dynamic $O(1)$-coloring for graphs with constant arboricity such as planar graphs or graphs with bounded tree-width, which is impossible using explicit colorings. We also show how to dynamically maintain a partition of the graph's edges into $O(α)$ forests with polylogarithmic update time. We believe this data structure is of independent interest and might have more applications in the future.
