Locally computing edge orientations

Slobodan Mitrović, Ronitt Rubinfeld, Mihir Singhal

We consider the question of orienting the edges in a graph $G$ such that every vertex has bounded out-degree. For graphs of arboricity $\alpha$, there is an orientation in which every v…