DOIAbstract
AbstractIn this paper, we present an algorithm for finding all common bases in two matroids. Our algorithm lists all common bases by using pivot operations in such a way that each basis appears exactly once. The time complexity of the algorithm is O(n(n2 + t)λ) where n is the size of the ground set of the matroids, λ is the number of common bases, and t is time to make one pivot operation. The space complexity is O(n2) and thus does not depend on λ As applications, we show how our algorithm can be applied to efficient enumerations of all complementary bases in the linear complementarity problem and all perfect matchings in a bipartite graph
Add to ORKG