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 -