کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949811 1364257 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximately counting paths and cycles in a graph
ترجمه فارسی عنوان
تقریبا شمارش مسیرها و چرخه ها در یک گراف
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the time complexity of problems of counting paths and cycles in a graph, respectively. We first show that these two problems are #P-hard. Then, we show an inapproximability result: there is no FPRAS for approximately counting paths and cycles in a graph, respectively unless RP=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 381-387
نویسندگان
,