Algorithms for Enumerating Circuits in Matroids.

Boros, Endre; Elbassioni, Khaled M.; Gurvich, Vladimir; Khachiyan, Leonid

doi:10.1007/978-3-540-24587-2_50

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Algorithms for Enumerating Circuits in Matroids.

MPS-Authors

/persons/resource/persons44374

Elbassioni, Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Boros, E., Elbassioni, K. M., Gurvich, V., & Khachiyan, L. (2003). Algorithms for Enumerating Circuits in Matroids. In Algorithms and Computation (pp. 485-494). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-ED43-6

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. This result implies, in particular, that for a given infeasible system of linear equations, all its maximal feasible subsystems, as well as all minimal infeasible subsystems, can be enumerated in incremental polynomial time. We also show the NP-hardness of several related enumeration problems.