کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872037 681717 2016 25 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The challenges of unbounded treewidth in parameterised subgraph counting problems
ترجمه فارسی عنوان
چالش های عرض نامحدود درخت در مشکلات شمارش پارامتریک زیرگراف
کلمات کلیدی
ترجمه چکیده
مسائل شمارش زیرگراف پارامتری شده، موضوعی است که بیشتر مورد بررسی قرار گرفته است در نظریه شمارش پارامترها، و پیشرفت های قابل توجهی در این زمینه وجود داشته است. بسیاری از رقیق بودن موجود برای مشکلات پارامتریک که شامل یافتن یا شمارش زیرگرافها با خصوصیات خاص است، به برخی از معیارها بستگی دارد که عرض عرض این زیرگرافها را محدود کند. در اینجا، ما تعدادی از نتایج سختی را برای وضعیتی که این شرط ضریب عرضی در آن ضعیف نیست، اثبات می کند و نتیجه برخی از موارد خاص در شمارش شمارنده ی زیر را دارد. این مقاله همچنین به بررسی کامل نتایج نتایج شناخته شده در این موضوع و روش های مورد استفاده و بحث در مورد روابط بین نسخه های چند رنگ و بدون رنگ با شمارش شمارنده و بین شمارش دقیق، شمارش تقریبی و مسائل مربوط به تصمیم گیری می پردازد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
چالش های عرض نامحدود درخت در مشکلات شمارش پارامتریک زیرگراف
چکیده انگلیسی
Parameterised subgraph counting problems are the most thoroughly studied topic in the theory of parameterised counting, and there has been significant recent progress in this area. Many of the existing tractability results for parameterised problems which involve finding or counting subgraphs with particular properties rely on bounding the treewidth of these subgraphs in some sense; here, we prove a number of hardness results for the situation in which this bounded treewidth condition does not hold, resulting in dichotomies for some special cases of the general subgraph counting problem. The paper also gives a thorough survey of known results on this subject and the methods used, as well as discussing the relationships both between multicolour and uncoloured versions of subgraph counting problems, and between exact counting, approximate counting and the corresponding decision problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 170-194
نویسندگان
,