An Augmenting Path Algorithm For The Parity Problem On Linear Matroids
Matthias F. M. Stallmann, Harold N. Gabow · 2005
The matroid parity problem is a generalization of matroid intersection and general graph matching (and hence network flow, degree-constrained subgraphs, etc.). A polynomial algorithm for linear matroids was presented by Lovasz. This paper presents an algorithm that uses time 0(mn/sup 3/), where m is the number of elements and n is the rank; for the spanning tree parity problem the time 0(mn/sup 2/). The algorithm is based on the method of augmenting paths used in the algorithms for all subcases of the problem.