کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874679 | 1441188 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reconfiguration on sparse graphs
ترجمه فارسی عنوان
تنظیم مجدد بر روی گرافهای نزولی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تنظیمات غرور مجموعه، مجموعه مستقل، نمودارهای انعطاف پذیر، پیچیدگی پارامتریک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set. We denote the former by and the latter by . Both and are PSPACE-complete on graphs of bounded bandwidth and W[1]-hard parameterized by k on general graphs. We show that is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 122-131
Journal: Journal of Computer and System Sciences - Volume 95, August 2018, Pages 122-131
نویسندگان
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.S. Ramanujan, Saket Saurabh,