TY - GEN

T1 - Degree-constrained graph orientation

T2 - 11th International Workshop on Approximation and Online Algorithms, WAOA 2013

AU - Asahiro, Yuichi

AU - Jansson, Jesper

AU - Miyano, Eiji

AU - Ono, Hirotaka

N1 - Funding Information:
Supported by KAKENHI Grant Numbers 21680001, 23500020, 25104521, and 25330018 and The Hakubi Project at Kyoto University.

PY - 2014

Y1 - 2014

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 [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -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. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.

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 [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -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. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.

UR - http://www.scopus.com/inward/record.url?scp=84903631659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903631659&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08001-7_3

DO - 10.1007/978-3-319-08001-7_3

M3 - Conference contribution

AN - SCOPUS:84903631659

SN - 9783319080000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 24

EP - 36

BT - Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers

PB - Springer Verlag

Y2 - 5 September 2013 through 6 September 2013

ER -