Adaptive Out-Orientations with Applications

Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm +4

We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the out-degree of each vertex is bounded. On one hand, we show how to orient the e…