TR-2016-10

Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation

Kristóf Bérczi, András Frank

Published in:
Mathematics of Operations Research 2018 43:3, 754-762. DOI link

Ryser's max term rank formula with graph theoretic terminology is equivalent to a characterization of degree sequences of simple bipartite graphs with matching number at least $\ell$. In a previous paper by the authors, a generalization was developed for the case when the degrees are constrained by upper and lower bounds. Here two other extensions of Ryser's theorem are discussed. The first one is a matroidal model, while the second one settles the augmentation version. In fact, the two directions shall be integrated into one single framework.

Bibtex entry:

@techreport{egres-16-10,

AUTHOR	=	{B{\'e}rczi, Krist{\'o}f and Frank, Andr{\'a}s},
TITLE	=	{Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2016},
NUMBER	=	{TR-2016-10}

}