Xref: utzoo comp.theory:1548 sci.math:15206
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!zaphod.mps.ohio-state.edu!rpi!crdgw1!cs.albany.edu!dcgu
From: dcgu@cs.albany.edu (DeChang Gu)
Newsgroups: comp.theory,sci.math
Subject: enumeration of minimum circuits
Keywords: minimum circuit, algorithm, upper bound
Message-ID: <611@odin.albany.edu>
Date: 19 Feb 91 15:33:50 GMT
Followup-To: poster
Organization: SUNY Albany, Comp Sci Dept, Albany, NY
Lines: 16

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