کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430994 | 688244 | 2012 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact exponential-time algorithm for the Directed Maximum Leaf Spanning Tree problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a directed graph G=(V,A)G=(V,A), the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree with as many leaves as possible. By designing a branching algorithm analyzed with Measure&Conquer , we show that the problem can be solved in time O⁎(1.9044n)O⁎(1.9044n) using polynomial space. Allowing exponential space, this run time upper bound can be lowered to O⁎(1.8139n)O⁎(1.8139n). We also provide an example showing a lower-bound for the running time of our algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 15, August 2012, Pages 43–55
Journal: Journal of Discrete Algorithms - Volume 15, August 2012, Pages 43–55
نویسندگان
Daniel Binkele-Raible, Henning Fernau,