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.
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||2nd International Symposium on Combinatorial Optimization, ISCO 2012|
|Period||19/04/12 → 21/04/12|
- Theoretical Computer Science
- Computer Science(all)