TR-2006-05

Hardness results for well-balanced orientations

Attila Bernáth



Abstract

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:

@techreport{egres-06-05,
AUTHOR = {Bern{\'a}th, Attila},
TITLE = {Hardness results for well-balanced orientations},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-05}
}


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