کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4634695 | 1340697 | 2008 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An efficient approximation algorithm for counting n-cycles in a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 196, Issue 1, 15 February 2008, Pages 479–482
Journal: Applied Mathematics and Computation - Volume 196, Issue 1, 15 February 2008, Pages 479–482
نویسندگان
Sheng Zhong,