Publication
Finding all common bases in two matroids
1995
Article
Article
Résumé
In 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(n^2+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, we show how our algorithm can be applied to efficient enumerations of all complementary bases in the linear complementary problem and all perfect matchings in a bipartite graph.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.