| Article ID: | iaor20084042 |
| Country: | Japan |
| Volume: | 50 |
| Issue: | 4 |
| Start Page Number: | 325 |
| End Page Number: | 338 |
| Publication Date: | Dec 2007 |
| Journal: | Journal of the Operations Research Society of Japan |
| Authors: | Boros Endre, Khachiyan Leonid, Makino Kazuhisa, Borys Konrad, Elbassioni Khaled, Gurvich Vladimir |
| Keywords: | computational analysis |
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.