Identifying Loops In Almost Linear Time

this paper, we study and improve three recently proposed algorithms for identifying loops in an irreducible graph. The first algorithm we study is due to Havlak [1997]. We show that the running time of this algorithm is quadratic in the worst-case, and not almost-linear as claimed. We then show how to modify the algorithm to make it run in almost Author's address: G. Ramalingam, IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY, 10598, USA. E-mail: rama@watson.ibm.co