ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS( the 50th Anniversary of the Operations Research Society of Japan)
Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir A. Gurvich, Kazuhisa Makino · Journal of the Operations Research Society of Japan · 2007
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.