Published in:
Combinatorica Volume 29, Number 5 (2009), 619-628.
This note extends the results of Frank, Jordán, and Szigeti on parity constrained orientations with connectivity requirements. Given a hypergraph H, a non-negative intersecting supermodular set function p, and a preferred in-degree parity for every node, a formula is given on the minimum number of nodes with wrong in-degree parity in an orientation of H covering p. It is shown that the minimum number of nodes with wrong in-degree parity in a strongly connected orientation cannot be characterized by a similar formula.
Bibtex entry:
@techreport{egres-03-11,
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Szab{\'o}, J{\'a}cint}, |
TITLE | = | {A note on parity constrained orientations}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2003}, |
NUMBER | = | {TR-2003-11} |