论文标题
完全动态的$α+ 2 $ ARBORICITY分解和隐性着色
Fully-dynamic $α+ 2$ Arboricity Decomposition and Implicit Colouring
论文作者
论文摘要
在隐式动态着色问题中，任务是维持适当的着色表示动态图，以插入和删除边缘的插入，同时促进散布的查询对顶点的颜色。目的是使用很少的颜色，同时仍然有效地处理边缘更新并响应颜色。对于N-Vertex动态图$α$的动态图，我们提出了一种算法，该算法以$ 4 \ cdot2^α$颜色保持隐式顶点着色，以摊销的poly-$（\ log n）$更新时间，以及$ o（αlog n log n）$ o（αlog n）$ worst-case cases Querst cases Query Query Query时间。以前的最佳隐式动态着色算法使用$ 2^{40α} $颜色，并且具有$ O（\ log^3 n）$的更有效更新时间，并且相同的查询时间为$ O（αlog n）$ [Henzinger et al'20]。 对于经历了支撑性$α$保留更新的图形，我们提供了一个完全动态的$α+2 $ poly $（\ log n，α）$时间的铝制分解，该森林的数量与Blumenstock and Fischer和Fischer [2020] $ 2 $ 2 $α+α+α+α+α+α+α+α+α+α+α+α+α+α+α;我们的构造是通过动态界限的户外方向进行的，在该方向上，我们提出了$ \ lfloor（1+ \ varepsilon）α\ rfloor + 2 $ bounded of-degredientation in fimest fiption $ o（f varepsilon^n n n formate offloor + 2 $ boffloor + 2 $ o（f varepsilon^n n n n n n og）$ + 2 $ o（1 + \ varepsilon）α\ rfloor + 2 $ o（\ varepsilon^n n n n n n n n n n n n n n n n n Nnne）最先进的明确，确定性的，最差的算法用于有限的外向取向，以$ o（β^2α^2+βα\log_βn）$β\ cdotα+ \log_βn $外向维持。
In the implicit dynamic colouring problem, the task is to maintain a representation of a proper colouring as a dynamic graph is subject to insertions and deletions of edges, while facilitating interspersed queries to the colours of vertices. The goal is to use few colours, while still efficiently handling edge-updates and responding to colour-queries. For an n-vertex dynamic graph of arboricity $α$, we present an algorithm that maintains an implicit vertex colouring with $4\cdot2^α$ colours, in amortised poly-$(\log n)$ update time, and with $O(α log n)$ worst-case query time. The previous best implicit dynamic colouring algorithm uses $2^{40α}$) colours, and has a more efficient update time of $O(\log^3 n)$ and the same query time of $O(α log n)$ [Henzinger et al'20]. For graphs undergoing arboricity $α$ preserving updates, we give a fully-dynamic $α+2$ arboricity decomposition in poly$(\log n,α)$ time, which matches the number of forests in the best near-linear static algorithm by Blumenstock and Fischer [2020] who obtain $α+2$ forests in near-linear time. Our construction goes via dynamic bounded out-degree orientations, where we present a fully-dynamic explicit, deterministic, worst-case algorithm for $\lfloor (1+\varepsilon)α\rfloor + 2$ bounded out-degree orientation with update time $O(\varepsilon^{-6}α^2 \log^3 n)$. The state-of-the-art explicit, deterministic, worst-case algorithm for bounded out-degree orientations maintains a $β\cdot α+ \log_β n$ out-orientation in $O(β^2α^2+βα\log_β n)$ time [Kopelowitz et al'13].
