TY - GEN
T1 - Graph orientations optimizing the number of light or heavy vertices
AU - Asahiro, Yuichi
AU - Jansson, Jesper
AU - Miyano, Eiji
AU - Ono, Hirotaka
N1 - Funding Information:
Funded by KAKENHI grant numbers 21680001, 22650004, 22700019, and 23500020 and The Hakubi Project at Kyoto University.
PY - 2012
Y1 - 2012
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
UR - http://www.scopus.com/inward/citedby.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 contribution
AN - SCOPUS:84865205428
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 -