# A Simple Greedy Algorithm for Dynamic Graph Orientation

## Edvin Berglin and Gerth Stølting Brodal

In * Proc. 28th Annual International Symposium on Algorithms and Computation*, volume 92 of * Leibniz International Proceedings in Informatics*, 12:1-12:12 pages. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2017.

## Abstract

*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 general 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*(\sqrt{log *n*}) flips nearly matching degree bounds to their respective amortized
solutions.

**Copyright notice**
Creative Commons License ND

**Online version**

isaac17.pdf (513 Kb)

**DOI**

10.4230/LIPIcs.ISAAC.2017.12

**BIBT**_{E}X entry

@incollection{isaac17,
author = "Edvin Berglin and Gerth St{\o}lting Brodal",
booktitle = "Proc. 28th Annual International Symposium on Algorithms and Computation",
doi = "10.4230/LIPIcs.ISAAC.2017.12",
isbn = "978-3-95977-054-5",
pages = "12:1-12:12",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f\"ur Informatik, Dagstuhl Publishing, Germany",
series = "Leibniz International Proceedings in Informatics",
title = "A Simple Greedy Algorithm for Dynamic Graph Orientation",
volume = "92",
year = "2017"
}