A simple greedy algorithm for dynamic graph orientation

Publikation: Forskning - peer reviewPaper

raph orientations with low out-degree are one of several ways to efficiently store sparse graphs.
If the graphs are dynamic, i.e. allow for insertion and deletion of edges, one may have to flip the
orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as
our sparsity measure. With an immensely simple greedy algorithm, we get parametrized trade-off
bounds with worst case number of flips, which previously only existed for amortized flips. We
match the previous best worst-case algorithm (in O(log n) flips) for general arboricity and beat
it when the arboricity is either constant or super-logarithmic. We also match a previous best
amortized algorithm for at least logarithmic arboricity, and give the first results with worst-case

O(1) and O( log n) flips respectively.
OriginalsprogEngelsk
Udgivelsesår31 aug. 2017
Antal sider11
StatusAccepteret/In press - 31 aug. 2017

Se relationer på Aarhus Universitet Citationsformater

ID: 117024200