English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Enumerating Spanning and Connected Subsets in Graphs and Matroids

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
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

Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., & Makino, K. (2006). Enumerating Spanning and Connected Subsets in Graphs and Matroids. In Algorithms - ESA 2006, 14th Annual European Symposium (pp. 444-455). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-22B3-A
Abstract
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.