2021/03/01 by Hongyu Zhou, Xinmin Hou, Zhou, Hongyu +1
Computer Science · Engineering · #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2103.01017
openalex publication_date 2021/03/01 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28
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) 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, that is we show that the algorithm SC-PATH-REVERSAL finds a strongly connected orientation that minimizes the lexicographic order of indegrees.