کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951160 | 1441195 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Faster exact algorithms for some terminal set problems
ترجمه فارسی عنوان
الگوریتم دقیق تر برای برخی از مشکلات ترمینال
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Many problems on graphs can be expressed in the following language: given a graph G=(V,E) and a terminal set TâV, find a minimum size set SâV which intersects all “structures” (such as cycles or paths) passing through the vertices in T. We refer to this class of problems as terminal set problems. In this paper, we introduce a general method to obtain faster exact exponential time algorithms for several terminal set problems. In the process, we break the Oâ(2n) barrier for the classic Node Multiway Cut, Directed Unrestricted Node Multiway Cut and Directed Subset Feedback Vertex Set problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 195-207
Journal: Journal of Computer and System Sciences - Volume 88, September 2017, Pages 195-207
نویسندگان
Rajesh Chitnis, Fedor V. Fomin, Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan, Saket Saurabh,