Finding all common bases in two matroids (Q1842654): Difference between revisions

Let \(E\) be a finite set and \(M_ 1\), \(M_ 2\) matroids on \(E\) with basis sets \(\beta_ 1\), \(\beta_ 2\) respectively. Given a \(B\in \beta_ 1\cap \beta_ 2\) the authors present an algorithm to determine the entire set \(\beta_ 1\cap \beta_ 2\). Estimates for the time and space complexity of this algorithm are given. In the final section applications of this algorithm to the linear complementarity problem and to the enumeration of all perfect matchings in a bipartite graph are presented.