Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the Barrier
En palabras de los autores
We study the dynamic edge orientation problem introduced in a seminal 1999 paper by Brodal and Fagerberg: given a fully dynamic graph with arboricity bounded by , maintain an orientation on 's edges so every vertex has out-degree upper bounded by a function of . They provided an algorithm with amortized update time that maintains an orientation with maximum out-degree . In the decades since, this algorithm has found widespread applications in dynamic graph algorithms. Nevertheless, it has remained a stubborn open question whether, when , the 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 orientation runs in amortized update time, which is an exponentially-improved dependence on . This is the first improvement on Brodal and Fagerberg's upper bound even for the 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.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 29 pages, 3 figures