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:

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}

Last modification: 16.10.2019. Please email your comments to TamŠs KirŠly!