کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4952328 1364440 2017 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
ترجمه فارسی عنوان
الگوریتم های دقیق برای مجموعه حداکثر انحلال و حداقل مسائل مربوط به مسائل مربوط به مسائل مربوط به مسائل مربوط به مسائل 3 بعدی
کلمات کلیدی
الگوریتم دقیق، الگوریتم نمودار، تعداد تلفات، پوشش 3 عنصر ریشه، برنامه نویسی دینامیک،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

A dissociation set in a graph G=(V,E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if V∖D is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in O⁎(1.4658n) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in O⁎(1.4656n) time and polynomial space or O⁎(1.3659n) time and exponential space.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 86-97
نویسندگان
, ,