Given two matroids M1=(E,ℐ1) and M2=(E,ℐ2), three algorithms for finding K best intersections I1,I2,...,IK are presented. The first version is a straightforward application of a general procedure due to Murty and Lawler. The complexity for finding I2,...,Ik is O(Km2R(R+c(m)+logm)) where m is the number of elements in E,R=min{r1(E),r2(E)}, and c(m) is the complexity of an independence oracle. By using maximum weighted border paths to computer second best intersections of modified matroids, this bound is reduced to O(K(m3+mRc(m))). Finally, a condensed version of the border graph is proposed to further improve the bound to O(KmRc(m)). The latter idea can also be used to find the optimal intersection IÅ1 in O(mR2c(m)) time, which is competitive with recent matroid intersection algorithms by Frank and Brezovec, Cornuejols, and Glover.
