CODEWITHSUNDEEP
algorithmgraphshortest-pathcycle
pearson boy
pearson boy

Reputation: 69

Are there any efficient algorithms for finding shortest cycle length?

Given problem : For given a undirected graph, find the shortest cycle of the length.

I found the O(E(ElogV)) algorithm, but it still so slow for solving the problem.

Are there any efficient algorithm for this problem?

Upvotes: 2

Views: 347

Answers (1)

modnar
modnar

Reputation: 274

The best known algorithm (due to Itai and Rodeh) for computing the length of a shortest cycle of an n-vertex graph takes time O(M(n) log n), where M(n) is the time required for multiplying two n-by-n matrices.

A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing,7(4):413–423, 1978.

Upvotes: 4

Related Questions