Article ID Journal Published Year Pages File Type
4634695 Applied Mathematics and Computation 2008 4 Pages PDF
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
,