论文标题
应用程序的自适应外向
Adaptive Out-Orientations with Applications
论文作者
论文摘要
我们提供了改进的算法，用于维持完全动态图的边缘方向，从而使每个顶点的外观有界限。一方面，我们展示了如何定向边缘，以使每个顶点的外观与图形的树木$α$成正比，在最差的案例更新时间为$ o（\ log^3 n \ loglogα）$。另一方面，以包括动态最大匹配在内的应用程序进行的激励，我们获得了不同的权衡，即改进的最坏情况更新时间为$ o（\ log ^2 n \logα）$，以确保最多可保持边缘定位的问题，最多可以$ o（α+ \\ log n）$ outtex。由于我们的算法具有更新的时间，并保证了最差的案例，因此解决方案的更改数（即追索）自然受到限制。我们的算法适应了图表的当前树木，并比以前的工作相比提高了效果：首先，我们获得了$ O（\ varepsilon^{ - 6} \ 6} \ log^3 n \ logρ）$最差的更新时间算法，用于维护$（1+ \ varepsilon）$ subpraph $ $ usprapph $ $ usprapph $ usplapph $ y的最大$ upphs。 其次，我们获得了一个$ o（\ varepsilon^{ - 6} \ log^3 n \logα）$ worst-case更新时间算法，用于维护$（1 + \ varepsilon）\ cdot opt + 2 $ 2 $近似图形的最佳范围，具有适应性的外观的最佳范围。这产生了用于分解为$ o（α）$ forest的第一个最坏情况的多族动态算法。三分之一，我们获得了各种问题，包括最大值匹配，包括$δ+1 $ 1 $ coloring和matrix vector乘，我们获得了各种问题的全动态确定性算法。所有更新时间均为最差案例$ o（α+\ log^2n \logα）$，其中$α$是该图的当前营养性。
We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the edges such that the out-degree of each vertex is proportional to the arboricity $α$ of the graph, in a worst-case update time of $O(\log^3 n \log α)$. On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off, namely the improved worst case update time of $O(\log ^2 n \log α)$ for the problem of maintaining an edge-orientation with at most $O(α+ \log n)$ out-edges per vertex. Since our algorithms have update times with worst-case guarantees, the number of changes to the solution (i.e. the recourse) is naturally limited. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain an $O(\varepsilon^{-6}\log^3 n \log ρ)$ worst-case update time algorithm for maintaining a $(1+\varepsilon)$ approximation of the maximum subgraph density, $ρ$. Secondly, we obtain an $O(\varepsilon^{-6}\log^3 n \log α)$ worst-case update time algorithm for maintaining a $(1 + \varepsilon) \cdot OPT + 2$ approximation of the optimal out-orientation of a graph with adaptive arboricity $α$. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into $O(α)$ forests.Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety, of problems including maximal matching, $Δ+1$ coloring, and matrix vector multiplication. All update times are worst-case $O(α+\log^2n \log α)$, where $α$ is the current arboricity of the graph.
