A simple greedy algorithm for dynamic graph orientation

Publication: Research - 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.
Original languageEnglish
Publication year31 Aug 2017
Number of pages11
StateAccepted/In press - 31 Aug 2017

See relations at Aarhus University Citationformats

ID: 117024200