DIMACS TR: 2003-17

On the Complexity of Some Enumeration Problems for Matroids



Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Leonid Khachiyan

ABSTRACT

We present an incremental polynomial-time algorithm for enumerating all circuits of a matroid or, more generally, all minimal spanning sets for a flat. We also show the NP-hardness of several related enumeration problems.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2003/2003-17.ps.gz
DIMACS Home Page