Efficient approximation algorithms for shortest cycles in undirected graphs
We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. For an undirected graph G of unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k + 2 for odd k, in time O(n(3/2) root logn). Thus, in general, it yields a 2 2/3 approximation. We study also the problem of finding a simple c
