TR-2008-10

A matroid intersection algorithm

Gyula Pap



Abstract

We propose an algorithm for Rado's min-max formula, which, by a polynomial reduction, also implies a polynomial time algorithm for matroid intersection. The algorithm is different from Edmonds', since here we do not use alternating paths, and instead, we exploit contractions of the matroid. We remark that Iwata, Takazawa [2] constructed an independent even factor algorithm that, as a special case, implies a similar matroid intersection algorithm. Further related algorithms have been proposed by the author for matching problems, see [3].


Bibtex entry:

@techreport{egres-08-10,
AUTHOR = {Pap, Gyula},
TITLE = {A matroid intersection algorithm},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-10}
}


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