Enumeration of Bases in Matroid with Exponentially Large Ground Set

Yuki Nishimura, Kazuya Haraguchi

When we deal with a matroid $\mathcal{M}=(U,\mathcal{I})$, we usually assume that it is implicitly given by means of the independence (IND) oracle. Time complexity of many existi…