Geodesic
Egalitarian Graph Orientations
Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 687-708.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00435
Keywords: algorithms, graph orientation, telecommunications 
@article{JGAA_2017_21_4_a13,
     author = {Glencora Borradaile and Jennifer Iglesias and Theresa Migler and Antonio Ochoa and Gordon Wilfong and Lisa Zhang},
     title = {Egalitarian {Graph} {Orientations}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {687--708},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2017},
     doi = {10.7155/jgaa.00435},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00435/}
}
TY  - JOUR
AU  - Glencora Borradaile
AU  - Jennifer Iglesias
AU  - Theresa Migler
AU  - Antonio Ochoa
AU  - Gordon Wilfong
AU  - Lisa Zhang
TI  - Egalitarian Graph Orientations
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 687
EP  - 708
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00435/
DO  - 10.7155/jgaa.00435
LA  - en
ID  - JGAA_2017_21_4_a13
ER  - 
%0 Journal Article
%A Glencora Borradaile
%A Jennifer Iglesias
%A Theresa Migler
%A Antonio Ochoa
%A Gordon Wilfong
%A Lisa Zhang
%T Egalitarian Graph Orientations
%J Journal of Graph Algorithms and Applications
%D 2017
%P 687-708
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00435/
%R 10.7155/jgaa.00435
%G en
%F JGAA_2017_21_4_a13
Glencora Borradaile; Jennifer Iglesias; Theresa Migler; Antonio Ochoa; Gordon Wilfong; Lisa Zhang. Egalitarian Graph Orientations. Journal of Graph Algorithms and Applications, Tome 21 (2017) no. 4, pp. 687-708. doi : 10.7155/jgaa.00435. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00435/

Cité par Sources :