کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951184 | 1441197 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized algorithms for min-max multiway cut and list digraph homomorphism
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We design FPT-algorithms for the following problems. The first is List Digraph Homomorphism: given two digraphs G and H, with order n and h, respectively, and a list of allowed vertices of H for every vertex of G, does there exist a homomorphism from G to H respecting the list constraints? Let â be the number of edges of G mapped to non-loop edges of H. The second problem is Min-Max Multiway Cut: given a graph G, an integer ââ¥0, and a set T of r terminals, can we partition V(G) into r parts such that each part contains one terminal and there are at most â edges with only one endpoint in this part? We solve both problems in time 2O(ââ
logâ¡h+â2â
logâ¡â)â
n4â
logâ¡n and 2O((âr)2logâ¡âr)â
n4â
logâ¡n, respectively, via a reduction to a new problem called List Allocation, which we solve adapting the randomized contractions technique of Chitnis et al. (2012) [4].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 86, June 2017, Pages 191-206
Journal: Journal of Computer and System Sciences - Volume 86, June 2017, Pages 191-206
نویسندگان
Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos,