Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4634695 | Applied Mathematics and Computation | 2008 | 4 Pages |
Abstract
Recently, Cash [G.G. Cash, The number of n-cycles in a graph, Applied Mathematics and Computation 184 (2007) 1080–1083] presents a method for counting the number of n-cycles in a graph. However, we point out that all methods for (precisely) counting n-cycles, including Cash’s, are super-polynomial-time, unless P = NP. This implies that it is unlikely to count n-cycles both precisely and efficiently. To solve this problem, we propose an efficient approximation algorithm. Our algorithm is guaranteed to finish in polynomial-time and has a reasonable error bound.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Sheng Zhong,