|
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-05} |