Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees
Hongyu Zhou, Xinmin Hou · International Journal of Foundations of Computer Science · 2022
Given a simple undirected graph [Formula: see text], an orientation of [Formula: see text] is to assign every edge of [Formula: see text] a direction. Borradaile et al gave a greedy algorithm SC-Path-Reversal (in polynomial time) which finds a strongly connected orientation that minimizes the maximum indegree, and conjectured that SC-Path-Reversal is indeed optimal for the ”minimizing the lexicographic order” objective as well. In this note, we give a positive answer to the conjecture, which is that we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.