کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420996 684015 2006 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On maximum planar induced subgraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On maximum planar induced subgraphs
چکیده انگلیسی

The nonplanar vertex deletion or vertex deletion vd(G)vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G   produces a planar graph G′G′. In this case G′G′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k  , to decide whether vd(G)⩽kvd(G)⩽k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k   satisfy vd(G)⩽kvd(G)⩽k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G)vd(G) when restricted to a cubic input G  . Finally, we exhibit a polynomial-time 34-approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 13, 15 August 2006, Pages 1774–1782
نویسندگان
, , , , ,