TR-2006-08

The parity problem of polymatroids without double circuits

Márton Makai, Jácint Szabó



Abstract

According to the present state of the theory of the matroid parity problem, the existence of a good characterization to the size of a maximum matching depends on the behavior of certain substructures, called double circuits. In this paper we prove that if a polymatroid has no double circuits then a partition type min-max formula characterizes the size of a maximum matching. Applications to parity constrained orientations and to a rigidity problem are given.


Bibtex entry:

@techreport{egres-06-08,
AUTHOR = {Makai, M{\'a}rton and Szab{\'o}, J{\'a}cint},
TITLE = {The parity problem of polymatroids without double circuits},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2006},
NUMBER = {TR-2006-08}
}


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