TY - JOUR
T1 - Degree-Constrained Graph Orientation
T2 - Maximum Satisfaction and Minimum Violation
AU - Asahiro, Yuichi
AU - Jansson, Jesper
AU - Miyano, Eiji
AU - Ono, Hirotaka
N1 - Funding Information:
This work was supported by KAKENHI grant numbers 23500020, 25104521, 25330018, 26330017, and 26540005 and The Hakubi Project at Kyoto University. The authors would like to thank the anonymous reviewers for their detailed comments and suggestions that helped to improve the presentation of the paper, and Peter Floderus for pointing out an error in one of the figures. An extended abstract of this paper appeared in Proceedings of the 11t hInternational Workshop on Approximation and Online Algorithms (WAOA 2013), volume 8447 of Lecture Notes in Computer Science , pp. 2436, Springer International Publishing Switzerland, 2014.
Publisher Copyright:
© 2014, Springer Science+Business Media New York.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).
AB - A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).
UR - http://www.scopus.com/inward/record.url?scp=84952985070&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84952985070&partnerID=8YFLogxK
U2 - 10.1007/s00224-014-9565-5
DO - 10.1007/s00224-014-9565-5
M3 - Article
AN - SCOPUS:84952985070
SN - 1432-4350
VL - 58
SP - 60
EP - 93
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 1
ER -