Changes
'''Theorem (Edmonds <ref>J. Edmonds, ''Submodular functions, matroids, and certain polyhedra'', In: R. Guy, H. Hanani, N. Sauer and J. Schönheim, Editors, Combinatorial Structures and Their Applications, Proceedings Calgary International Conference on Combinatorial Structures and Their Applications, Calgary, Alberta, June 1969, Gordon and Breach, New York (1970), pp. 69–87. [http://dx.doi.org/10.1007/3-540-36478-1_2 DOI link (LNCS version)].</ref>).''' Let <math>M_1=(S,r_1)</math> and <math>M_2=(S,r_2)</math> be two matroids. Then the maximum size of a common independent set of <math>M_1</math> and <math>M_2</math> is <math>\min_{X \subseteq S} (r_1(X)+r_2(S \setminus X)).</math>
This can be derived from [[Matroid union theorem]], and vice versa. There are several efficient algorithms for finding a maximum size common independent set: Cunningham<ref>W. H. Cunningham, ''Improved bounds for matroid partition and intersection algorithms'', [http://dx.doi.org/10.1137/0215066 DOI link].</ref> gave an algorithm that needs <math>O(n r^{1.5})</math> oracle calls, and Harvey<ref>N. J. A. Harvey, ''Algebraic algorithms for matching and matroid problems'', [http://dx.doi.org/10.1137/070684008 DOI link].</ref> presented a randomized algorithm for linear matroids with running time <math>O(nr^{\omega-1})</math>, where ''r'' is the rank and <math>\omega</math> is the matrix multiplication exponent.
==References==
