Algorithms for Enumerating Circuits in Matroids.

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

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

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Konferenzbeitrag

Algorithms for Enumerating Circuits in Matroids.

MPG-Autoren

/persons/resource/persons44374

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

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

Es sind keine frei zugänglichen Volltexte in PuRe verfügbar

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

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.

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

Zusammenfassung

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.