Publication

Finding all common bases in two matroids

1995
Journal paper
Abstract

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.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.