کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871356 | 1440184 | 2018 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
PTAS for H-free node deletion problems in disk graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
For a set H of graphs, a graph G is H-free if G does not contain any subgraph isomorphic to some graph in H. In this paper, we study the minimum H-free node deletion problem (MinHFND) and the maximum H-free node set problem (MaxHFNS), which include a lot of extensively-studied problems such as the minimum k-path vertex cover problem, the dissociation number problem, and the minimum degree bounded node deletion problem. For a large class of H, PTASs are given for MinHFND and MaxHFNS on disk graphs whose heterogeneity is bounded by a constant, where the heterogeneity of a disk graph is the ratio of the maximum radius to the minimum radius of disks.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 119-124
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 119-124
نویسندگان
Xiaosong Li, Yishuo Shi, Xiaohui Huang,