کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333913 | 689839 | 2011 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact algorithm for the Maximum Leaf Spanning Tree problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given an undirected graph with n vertices, the Maximum Leaf Spanning Tree problem is to find a spanning tree with as many leaves as possible. When parameterized in the number of leaves k, this problem can be solved in time O(4kpoly(n)) using a simple branching algorithm introduced by a subset of the authors (Kneis et al. 2008 [16]). Daligault et al. (2010) [6] improved the branching and obtained a running time of O(3.72kpoly(n)). In this paper, we study the problem from an exponential time viewpoint, where it is equivalent to the Connected Dominating Set problem. Here, Fomin, Grandoni, and Kratsch showed how to break the Ω(2n) barrier and proposed an O(1.9407n)-time algorithm (Fomin et al. 2008 [11]). Based on some useful properties of Kneis et al. (2008) [16] and Daligault et al. (2010) [6], we present a branching algorithm whose running time of O(1.8966n) has been analyzed using the Measure-and-Conquer technique. Finally, we provide a lower bound of Ω(1.4422n) for the worst case running time of our algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6290-6302
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6290-6302
نویسندگان
Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith,