Hardness results for well-balanced orientations

Attila Bernáth


In 1960 Nash-Williams proved his strong orientation theorem about the existence of well-balanced orientations. In this paper we show that it is NP-hard to find a minimum cost well-balanced orientation (given the cost for the two possible orientations of each edge) or a well-balanced orientation satisfying lower and upper bounds on the out-degrees at each node. Similar results are proved for best-balanced orientations and other related problems are considered, too.

Bibtex entry:

AUTHOR = {Bern{\'a}th, Attila},
TITLE = {Hardness results for well-balanced orientations},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-05}

Last modification: 5.6.2018. Please email your comments to Tamás Király!