کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950636 | 1440714 | 2017 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
ترجمه فارسی عنوان
جستجوی محلی عمیق تر برای الگوریتم های پارامتر شده و تقریبی برای حداکثر درخت پوشا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
حداکثر درخت درختی درختی محاسبه پارامتری، جستجوی محلی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The maximum internal spanning tree problem asks for a spanning tree of a given graph that has the maximum number of internal vertices among all spanning trees of this graph. In its parameterized version, we are interested in whether the graph has a spanning tree with at least k internal vertices. Fomin et al. (2013) [4] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel, implying an Oâ(8k)-time parameterized algorithm. Using depth-2 local search, Knauer and Spoerhase (2015) [9] developed a (5/3)-approximation algorithm for the optimization version. We try deeper local search: We conduct a thorough combinatorial analysis on the obtained spanning trees and explore their algorithmic consequences. We first observe that from the spanning tree obtained by depth-3 local search, one can easily find a reducible structure and apply the reduction rule of Fomin et al. This gives an improved kernel of 2k vertices, and as a by-product, a deterministic algorithm running in time Oâ(4k). We then go even deeper by considering the spanning tree obtained by depth-5 local search. It is shown that the number of internal vertices of this spanning tree is at least 2/3 of the maximum number a spanning tree can have, thereby delivering an improved approximation algorithm with ratio 1.5 for the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 252, February 2017, Pages 187-200
Journal: Information and Computation - Volume 252, February 2017, Pages 187-200
نویسندگان
Wenjun Li, Yixin Cao, Jianer Chen, Jianxin Wang,