Finding all common bases in two matroids

Finding all common bases in two matroids

0.00 Avg rating0 Votes
Article ID: iaor1996295
Country: Netherlands
Volume: 56
Issue: 2/3
Start Page Number: 231
End Page Number: 243
Publication Date: Jan 1995
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: graphs
Abstract:

In this paper, the authors present an algorithm for finding all common bases in two matroids. The 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(n’2) and thus does not depend on λ. As applications, the authors show how the algorithm can be applied to efficient enumerations of all complementary bases in the linear complementarity problem and all perfect matchings in a bipartite graph.

Reviews

Required fields are marked *. Your email address will not be published.