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 -