Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!csc!bdm659
From: bdm659@csc.anu.oz
Newsgroups: comp.theory
Subject: Re: finding all cycles in a directed graph
Message-ID: <1744.25ff97d4@csc.anu.oz>
Date: 15 Mar 90 13:25:40 GMT
References: <1153@laas.laas.fr>
Organization: Computer Services, Australian National University
Lines: 14

In article <1153@laas.laas.fr>, paul@laas.fr (Paul Freedman) writes:
> I'm looking for pointers to algorithms for
> finding ALL cycles in a directed graph.
> By `cycle', I mean a simple closed path which respects the
> orientation of the arcs.

This problem has a long history.  For example, try
J. L. Szwarcfiter and P. E. Lauer, A search strategy for the elementary
cycles of a directed graph, BIT 16 (1976) 192-204.

They do it in time O(n + m*(c + 1)), where n,m and c are the numbers of
vertices, edges and cycles, respectively.

Brendan McKay.  bdm@anucsd.oz.au  or  bdm659@csc1.anu.oz.au