TR-2003-11

A note on parity constrained orientations

Tamás Király, Jácint Szabó

Published in:
Combinatorica Volume 29, Number 5 (2009), 619-628.



Abstract

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}
}


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