Skip to main content
added link to Alon, Yuster and Zwick paper and fixed typos.
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Is there any result about the time complexity of finding a cycle of fixed length k$k$ in a general graph? All I know is that Noga Alon et al.Alon, Yuster and Zwick use the techiniquea technique called "color-coding", which has a running time O(M(n))of $O(M(n))$, where M(n)$n$ is the timenumber of multiplyingvertices of the input graph and $M(n)$ is the time required to multiply two n times n$n \times n$ matrices.

Is there any better result?

Is there any result about the time complexity of finding a cycle of fixed length k in a general graph? All I know is that Noga Alon et al. use the techinique called "color-coding", which has a running time O(M(n)), where M(n) is the time of multiplying two n times n matrices.

Is there any better result?

Is there any result about the time complexity of finding a cycle of fixed length $k$ in a general graph? All I know is that Alon, Yuster and Zwick use a technique called "color-coding", which has a running time of $O(M(n))$, where $n$ is the number of vertices of the input graph and $M(n)$ is the time required to multiply two $n \times n$ matrices.

Is there any better result?

edited tags
Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53
Source Link

Finding a cycle of fixed length

Is there any result about the time complexity of finding a cycle of fixed length k in a general graph? All I know is that Noga Alon et al. use the techinique called "color-coding", which has a running time O(M(n)), where M(n) is the time of multiplying two n times n matrices.

Is there any better result?