کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871506 1440187 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A faster parameterized algorithm for Pseudoforest Deletion
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A faster parameterized algorithm for Pseudoforest Deletion
چکیده انگلیسی
A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O(3knkO(1)) time: given a graph G and an integer k, can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7.56knO(1)-time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 42-56
نویسندگان
, , ,