کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436296 689986 2014 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A feedback vertex set of 2-degenerate graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A feedback vertex set of 2-degenerate graphs
چکیده انگلیسی

A feedback vertex set of a graph G is a set S   of its vertices such that the subgraph induced by V(G)∖SV(G)∖S is a forest. The cardinality of a minimum feedback vertex set of G   is denoted by ∇(G)∇(G). A graph G is 2-degenerate   if each subgraph G′G′ of G has a vertex v   such that dG′(v)≤2dG′(v)≤2.In this paper, we prove that ∇(G)≤2n/5∇(G)≤2n/5 for any 2-degenerate n-vertex graph G and moreover, we show that this bound is tight. As a consequence, we derive a polynomial time algorithm, which for a given 2-degenerate n  -vertex graph returns its feedback vertex set of cardinality at most 2n/52n/5.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 557, 6 November 2014, Pages 50–58
نویسندگان
, , ,