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