elementary cycle detection

Graham Jones <gxj@dcs.ed.ac.uk>
Mon, 15 Nov 1993 17:11:12 GMT

          From comp.compilers

Related articles
elementary cycle detection gxj@dcs.ed.ac.uk (Graham Jones) (1993-11-15)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Graham Jones <gxj@dcs.ed.ac.uk>
Keywords: theory
Organization: Department of Computer Science, University of Edinburgh
Date: Mon, 15 Nov 1993 17:11:12 GMT

I have manged to find a paper that gives an algorithm for detecting
elementary cycles in O(N+M(C+1) time, where N is the number of vertices,
M is number of edges and C the number of elementary cycles. Does anyone
know of an improvement on this algorithm.

The paper : "a search strategy for the elementary cycles of a directed graph"
by J.L. Szwarcfiter and P.E. Lauer, BIT 16 1976 192--204.

  Graham P. Jones
  Address: Room 3419,
The University Of Edinburgh,
Kings Buildings,
West Mains Road,
Edinburgh EH9 3JY
  Tel : 031-650-5118

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.