Enumerating spanning and connected subsets in graphs and matroids

Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.

Original languageBritish English
Pages (from-to)325-338
Number of pages14
JournalJournal of the Operations Research Society of Japan
Issue number4
StatePublished - Dec 2007


  • Algorithm
  • Enumeration
  • Matroid
  • Quasi-polynomial


Dive into the research topics of 'Enumerating spanning and connected subsets in graphs and matroids'. Together they form a unique fingerprint.

Cite this