跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.10161 · v1

Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier

首次提交 2026-11-07 03:32
版本更新 2026-11-07 03:32
雷达观测 2026-11-10 10:11
arXiv ↗PDF ↗

摘要

We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph GG with arboricity bounded by αα, maintain an orientation on GG's edges so every vertex has out-degree upper bounded by a function of αα. They provided an algorithm with O(α+log⁡n)O(α+ \log n) amortized update time that maintains an orientation with maximum out-degree O(α)O(α). In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when α=o(log⁡n)α= o(\log n), the O(log⁡n)O(\log n) upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree O(α)O(α) orientation runs in O(α⋅log⁡log⁡n)O(α\cdot \log \log n) amortized update time, which is an exponentially-improved dependence on nn. This is the first improvement on Brodal and Fagerberg's upper bound even for the α=1α=1 case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.

作者备注:29 pages, 3 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-07 03:32 · 最新观测版本

Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the $\log n$ Barrier

We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph GG with arboricity bounded by αα, maintain an orientation on GG's edges so every vertex has out-degree upper bounded by a function of αα. They provided an algorithm with O(α+log⁡n)O(α+ \log n) amortized update time that maintains an orientation with maximum out-degree O(α)O(α). In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when α=o(log⁡n)α= o(\log n), the O(log⁡n)O(\log n) upper bound can be improved. We answer this 27-year-old question in the affirmative, showing that Brodal and Fagerberg's algorithm for maintaining an out-degree O(α)O(α) orientation runs in O(α⋅log⁡log⁡n)O(α\cdot \log \log n) amortized update time, which is an exponentially-improved dependence on nn. This is the first improvement on Brodal and Fagerberg's upper bound even for the α=1α=1 case of dynamic forests. Our crucial technical innovation is to construct a hierarchy of dynamic graphs with a property we call near isolation. We believe that this construction may be useful for related problems.

查看此版本解读 →查看此版本原文 ↗