Algorithms for enumerating circuits in matroids

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

Research output: Chapter in Book/Report/Conference proceedingChapter

8 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsToshihide Ibaraki, Naoki Katoh, Hirotaka Ono
PublisherSpringer Verlag
Pages485-494
Number of pages10
ISBN (Electronic)9783540206958
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2906
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Algorithms for enumerating circuits in matroids'. Together they form a unique fingerprint.

Cite this