کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431091 | 688270 | 2010 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We present subexponential parameterized algorithms on planar graphs for a family of problems of the following shape: given a graph, find a connected (induced) subgraph with bounded maximum degree and with maximum number of edges (or vertices). These problems are natural generalisations of the Longest Path problem. Our approach uses bidimensionality theory combined with novel dynamic programming techniques over branch decompositions of the input graph. These techniques can be applied to a more general family of problems that deal with finding connected subgraphs under certain degree constraints.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 8, Issue 3, September 2010, Pages 330–338
Journal: Journal of Discrete Algorithms - Volume 8, Issue 3, September 2010, Pages 330–338
نویسندگان
Ignasi Sau, Dimitrios M. Thilikos,