Efficient algorithms for independent assignment on graphic and linear matroids
Harold N. Gabow, Ying Xu · 1989
Efficient algorithms are presented for the matroid intersection problem and generalizations. The algorithm for weighted intersection works by scaling the weights. The cardinality algorithm is a special case that takes advantage of greater structure. Efficiency of the algorithms is illustrated by several implementations. On graphic matroids the algorithms run close to the best bounds for trivial matroids (i.e. ordinary bipartite graph matching): O( square root nm log n) for cardinality intersection and O( square root nm log/sup 2/n log(nN)) for weighted intersection (n, m, and N denote the number of vertices, edges, and largest edge weight, respectively; weights are assumed integral). Efficient algorithms are also given for linear matroids. These include both algorithms that are practical and algorithms exploiting fast matrix multiplication.>