کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952440 | 1442034 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized complexity of critical node cuts
ترجمه فارسی عنوان
پیچیدگی پارامترهای گره انتقادی را کاهش می دهد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات برش گراف درخت عرض کرنل کردن،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(κ)â
nO(1) time (i.e., whether or not it is fixed-parameter tractable), for various natural parameters κ. We consider four such parameters:
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 62-75
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 62-75
نویسندگان
Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, Barak Navon,