dcgu@cs.albany.edu (DeChang Gu) (02/19/91)
I am interested in finding answers to the following problems. Given an undirected graph G, is there an algorithm polynomial in the size of G, for enumerating all the minimum simple circuits in G? Given G as above, and k, the length of minimum circuit in G, how many simple circuits with length between k and 2k are there in G? Is there a known upper bound on this quantity for arbitrary G? And again, can we enumerate all such circuits in polynomial time? Any solution and/or pointer to relevant references will be highly appreciated. -- Dechang
pi@quark.isi.edu (Jen-I Pi) (02/20/91)
In article <611@odin.albany.edu>, dcgu@cs.albany.edu (DeChang Gu) writes: |> I am interested in finding answers to the following problems. |> |> Given an undirected graph G, is there an algorithm |> polynomial in the size of G, for enumerating all the |> minimum simple circuits in G? Yes! See the following reference for detail.... @article{Mateti76, author="P. Mateti and N. Deo", title="On Algorithms for Enumerating All Circuits of a Graph", journal="SIAM Journal of Computing", month="March", year=1976, volume=5, number=1, pages={90--99} } Hope this helps, regards! Jen-I pi@vlsi-cad.isi.edu :-)