[sci.math] enumeration of minimum circuits

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