Algorithms for enumerating circuits in matroids

Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Leonid Khachiyan

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

Algorithms for enumerating circuits in matroids

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan

Rutgers Business School, Management & Information Systems

Research output: Chapter in Book/Report/Conference proceeding › Chapter

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 language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono
Publisher	Springer Verlag
Pages	485-494
Number of pages	10
ISBN (Electronic)	9783540206958
DOIs	https://doi.org/10.1007/978-3-540-24587-2_50
State	Published - 2003

Publication series

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

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

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

Cite this

Boros, E., Elbassioni, K., Gurvich, V., & Khachiyan, L. (2003). Algorithms for enumerating circuits in matroids. In T. Ibaraki, N. Katoh, & H. Ono (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 485-494). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2906). Springer Verlag. https://doi.org/10.1007/978-3-540-24587-2_50

Boros, Endre ; Elbassioni, Khaled ; Gurvich, Vladimir et al. / Algorithms for enumerating circuits in matroids. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Toshihide Ibaraki ; Naoki Katoh ; Hirotaka Ono. Springer Verlag, 2003. pp. 485-494 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{332a4ef138c9450ba785392680982957,

title = "Algorithms for enumerating circuits in matroids",

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.",

author = "Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Leonid Khachiyan",

year = "2003",

doi = "10.1007/978-3-540-24587-2_50",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "485--494",

editor = "Toshihide Ibaraki and Naoki Katoh and Hirotaka Ono",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Boros, E, Elbassioni, K, Gurvich, V & Khachiyan, L 2003, Algorithms for enumerating circuits in matroids. in T Ibaraki, N Katoh & H Ono (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2906, Springer Verlag, pp. 485-494. https://doi.org/10.1007/978-3-540-24587-2_50

Algorithms for enumerating circuits in matroids. / Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir et al.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Toshihide Ibaraki; Naoki Katoh; Hirotaka Ono. Springer Verlag, 2003. p. 485-494 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2906).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Algorithms for enumerating circuits in matroids

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Khachiyan, Leonid

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35248852015&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35248852015&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24587-2_50

DO - 10.1007/978-3-540-24587-2_50

M3 - Chapter

AN - SCOPUS:35248852015

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 485

EP - 494

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Ibaraki, Toshihide

A2 - Katoh, Naoki

A2 - Ono, Hirotaka

PB - Springer Verlag

ER -

Boros E, Elbassioni K, Gurvich V, Khachiyan L. Algorithms for enumerating circuits in matroids. In Ibaraki T, Katoh N, Ono H, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 485-494. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24587-2_50

Algorithms for enumerating circuits in matroids

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this