A Simple Greedy Algorithm for Dynamic Graph Orientation

Edvin Berglin*, Gerth Stølting Brodal

*Corresponding author for this work

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review


Graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs 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 between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in O(log n) flips) for almost all values of arboricity and beat it for either constant or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O(1) and O(logn) flips nearly matching out-degree bounds to their respective amortized solutions.

Original languageEnglish
Pages (from-to)245-259
Number of pages15
Publication statusPublished - Feb 2020


  • Dynamic graph algorithms
  • Edge orientations
  • Graph arboricity


Dive into the research topics of 'A Simple Greedy Algorithm for Dynamic Graph Orientation'. Together they form a unique fingerprint.

Cite this