Strongly connected orientation with minimum lexicographic order of indegrees

Hongyu Zhou, Xinmin Hou

Given a simple undirected graph $G$, an orientation of $G$ is to assign every edge of $G$ a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time…