TY - GEN
T1 - Graph orientations optimizing the number of light or heavy vertices
AU - Asahiro, Yuichi
AU - Jansson, Jesper Andreas
AU - Miyano, Eiji
AU - Ono, Hirotaka
PY - 2012/8/27
Y1 - 2012/8/27
N2 - This paper introduces four graph orientation problems named Maximize W -Light, Minimize W -Light, Maximize W -Heavy, and Minimize W -Heavy, where W can be any fixed non-negative integer. In each of these problems, the input is an undirected graph G and the objective is to assign a direction to each edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. We derive a number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs. In particular, we show that Maximize 0-Light and Minimize 1-Heavy are equivalent to Maximum Independent Set and Minimum Vertex Cover, respectively, so by allowing the value of W to vary, we obtain a new, natural generalization of the two latter problems.
AB - This paper introduces four graph orientation problems named Maximize W -Light, Minimize W -Light, Maximize W -Heavy, and Minimize W -Heavy, where W can be any fixed non-negative integer. In each of these problems, the input is an undirected graph G and the objective is to assign a direction to each edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. We derive a number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs. In particular, we show that Maximize 0-Light and Minimize 1-Heavy are equivalent to Maximum Independent Set and Minimum Vertex Cover, respectively, so by allowing the value of W to vary, we obtain a new, natural generalization of the two latter problems.
UR - http://www.scopus.com/inward/record.url?scp=84865205428&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32147-4_30
DO - 10.1007/978-3-642-32147-4_30
M3 - Conference article published in proceeding or book
SN - 9783642321467
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 332
EP - 343
BT - Combinatorial Optimization - Second International Symposium, ISCO 2012, Revised Selected Papers
T2 - 2nd International Symposium on Combinatorial Optimization, ISCO 2012
Y2 - 19 April 2012 through 21 April 2012
ER -