کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952438 1442034 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of dominating set reconfiguration
ترجمه فارسی عنوان
پیچیدگی غالب تنظیم مجدد تنظیم
کلمات کلیدی
پیکربندی ترکیبی، غرور مجموعه، الگوریتم نمودار،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Suppose that we are given two dominating sets Ds and Dt of a graph G whose cardinalities are at most a given threshold k. Then, we are asked whether there exists a sequence of dominating sets of G between Ds and Dt such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O(n), where n is the number of vertices in the input graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 651, 25 October 2016, Pages 37-49
نویسندگان
, , , , , , ,