QP-2007-01

Well-balanced orientations of mixed graphs

Attila Bernáth, Gwenaël Joret

We show that deciding if a mixed graph has a well-balanced orientation is NP-complete.

Bibtex entry:

@techreport{egresqp-07-01,

AUTHOR	=	{Bern{\'a}th, Attila and Joret, Gwenaël},
TITLE	=	{Well-balanced orientations of mixed graphs},
NOTE	=	{{\tt www.cs.elte.hu/egres}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2007},
NUMBER	=	{QP-2007-01}

}