|
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:
| AUTHOR | = | {Makai, M{\'a}rton and Szab{\'o}, J{\'a}cint}, |
| TITLE | = | {The parity problem of polymatroids without double circuits}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2006}, |
| NUMBER | = | {TR-2006-08} |