Publication: Research - peer-review › Paper

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.

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 language | English |
---|---|

Publication year | 31 Aug 2017 |

Number of pages | 11 |

State | Accepted/In press - 31 Aug 2017 |

See relations at Aarhus University Citationformats

ID: 117024200