کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871709 | 1440189 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The (k,â)partitioned probe problem: NP-complete versus polynomial dichotomy
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The (k,â)partitioned probe problem: NP-complete versus polynomial dichotomy The (k,â)partitioned probe problem: NP-complete versus polynomial dichotomy](/preview/png/6871709.png)
چکیده انگلیسی
A graph G=(V,E) is Cprobe if V can be partitioned into two sets, probesP and non-probesN, where N is independent and new edges may be added between non-probes such that the resulting graph is in the graph class C. We say that (N,P) is a Cprobe partition for G. The Cpartitioned probe problem consists of an input graph G with a vertex partition (N,P) and the question: Is (N,P) a C probe partition for G? A (k,â)-partition of a graph G is a partition of its vertex set into at most k independent sets and â cliques. A graph is (k,â) if it has a (k,â)-partition. We prove that the Cpartitioned probe problem is polynomial for (1,2) and for (2,1)-graphs, and NP-complete for (2,2)-graphs. The results give the first graph class for which the partitioned probe problem is NP-complete, and the full complexity dichotomy into NP-complete and polynomial for (k,â)partitioned probe problems: they are NP-complete if k2+â2â¥8, and polynomial otherwise.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 67-75
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 67-75
نویسندگان
Simone Dantas, Luerbio Faria, Celina M.H. de Figueiredo, Rafael B. Teixeira,