Questions tagged [matroids]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1
votes
0answers
35 views

Complexity of Independence Oracle for Matroids

I am interested in the computational complexity of an independence Oracle for Matroids. In particular, I would like to know how efficiently such an Oracle can be implemented for Matroids with ...
0
votes
0answers
21 views

Going from one base packing to another using basis exchanges

Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...