کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333865 | 689653 | 2016 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The maximum infection time in the geodesic and monophonic convexities
ترجمه فارسی عنوان
حداکثر زمان آلودگی در تخلخل های ژئودزی و مونوفونیک
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محدب جغرافیایی، حداکثر زمان آلودگی تعداد مونوفونیک بدنه، محدب مونوفونیک،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Recent papers investigated the maximum infection time tP3(G) of the P3-convexity (also called maximum time of 2-neighbor bootstrap percolation) and the maximum infection time tmo(G) of the monophonic convexity. In 2014, it was proved that, for bipartite graphs, deciding whether tP3(G)â¥k is polynomial time solvable for kâ¤4, but is NP-complete for kâ¥5[23]. In 2015, it was proved that deciding whether tmo(G)â¥2 is NP-complete even for bipartite graphs [12]. In this paper, we investigate the maximum infection time tgd(G) of the geodesic convexity. We prove that deciding whether tgd(G)â¥k is polynomial time solvable for k=1, but is NP-complete for kâ¥2 even for bipartite graphs. We also present an O(n3m)-time algorithm to determine tgd(G) and tmo(G) in distance-hereditary graphs. For this, we characterize all minimal hull sets of a general graph in the monophonic convexity. Moreover, we improve the complexity of the fastest known algorithm for finding a minimum hull set of a general graph in the monophonic convexity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 287-295
Journal: Theoretical Computer Science - Volume 609, Part 2, 4 January 2016, Pages 287-295
نویسندگان
FabrÃcio Benevides, Victor Campos, Mitre C. Dourado, Rudini M. Sampaio, Ana Silva,