Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00371
Graph Orientations Optimizing the Number of Light or Heavy Vertices
Vol. 19, no. 1, pp. 441465, 2015. Regular paper.
Abstract This paper introduces four graph orientation problems named MAXIMIZE WLIGHT, MINIMIZE WLIGHT, MAXIMIZE WHEAVY, and MINIMIZE WHEAVY, where W can be any fixed nonnegative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every 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. A number of results on the computational complexity and polynomialtime approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0LIGHT and MINIMIZE 1HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems.

Submitted: May 2014.
Reviewed: July 2015.
Revised: August 2015.
Accepted: September 2015.
Final: September 2015.
Published: October 2015.
Communicated by
Kenichi Kawarabayashi
