bdm659@csc.anu.oz (03/15/90)
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
park@usceast.cs.scarolina.edu (Kihong Park) (03/16/90)
In article <3141@usceast.UUCP> park@usceast.UUCP (Kihong Park) writes: >The following problem relates(sort of) to your question: > > Given a directed graph G=<V,E> and a positive integer K <= |V|, does >there exist a subset of V, V', such that every cycle in G contains at >least one vertex from V', and |V'| <= K ? Ups, sorry for the above posting. It does not relate to your question at all. I must have been in a haze. The above is a decision problem whereas yours is not. I belief the posting referring to a O(|V| + |E|*|C|) algorithm where |C| is the number of cycles is the one you would be looking for.