Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00435
Egalitarian Graph Orientations
Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, and Lisa Zhang
Vol. 21, no. 4, pp. 687-708, 2017. Regular paper.
Abstract Given an undirected graph, one can assign directions to each of the edges of the graph, thus orienting the graph. To be as egalitarian as possible, one may wish to find an orientation such that no vertex is unfairly hit with too many arcs directed into it. We discuss how this objective arises in problems resulting from telecommunications. We give optimal, polynomial-time algorithms for: finding an orientation that minimizes the lexicographic order of the indegrees and finding a strongly-connected orientation that minimizes the maximum indegree. We show that minimizing the lexicographic order of the indegrees is NP-hard when the resulting orientation is required to be acyclic.
Submitted: July 2016.
Reviewed: October 2016.
Revised: December 2016.
Reviewed: March 2017.
Revised: May 2017.
Accepted: May 2017.
Final: May 2017.
Published: June 2017.
Communicated by Anna Lubiw
article (PDF)
BibTeX