کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952165 | 1442013 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exact exponential algorithms to find tropical connected sets of minimum size
ترجمه فارسی عنوان
الگوریتم های دقیق نمایشی برای یافتن مجموعه های وابسته به گرمسیری از حداقل اندازه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، نمودارها، الگوریتم های دقیق نمایشی، نمودارهای رنگی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The input of the Tropical Connected Set problem is a vertex-colored graph (G,c), where G=(V,E) is a graph and c is a vertex coloring assigning to each vertex of G a color. The task is to find a connected subset SâV of minimum size such that each color of G appears in S. This problem is known to be NP-complete, even when restricted to trees of height at most three. We study exact exponential algorithms to solve Tropical Connected Set. We present an Oâ(1.5359n) time algorithm for general graphs and an Oâ(1.2721n) time algorithm for trees. We also show that Tropical Connected Set on trees has no sub-exponential algorithm unless the Exponential Time Hypothesis fails.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 676, 9 May 2017, Pages 33-41
Journal: Theoretical Computer Science - Volume 676, 9 May 2017, Pages 33-41
نویسندگان
Mathieu Chapelle, Manfred Cochefert, Dieter Kratsch, Romain Letourneur, Mathieu Liedloff,