Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!apple!usc!isi.edu!vlsi-cad.isi.edu!pi
From: pi@quark.isi.edu (Jen-I Pi)
Newsgroups: comp.theory
Subject: Re: enumeration of minimum circuits
Keywords: minimum circuit, algorithm, upper bound
Message-ID: <16836@venera.isi.edu>
Date: 20 Feb 91 05:51:00 GMT
References: <611@odin.albany.edu>
Sender: news@isi.edu
Reply-To: pi@vlsi-cad.isi.edu (Jen-I Pi)
Organization: USC/ISI (Information Science Institute)
Lines: 19

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


Brought to you by Super Global Mega Corp .com