[comp.theory] 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

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 :-)