کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652614 | 1632594 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomial reductions between the Limited Packing and Tuple Domination problems in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The Limited Packing and Tuple Domination problems in graphs have closely-related definitions and the same computational complexity on several graph classes. In this work we present two polynomial reductions between these problems. Thus, by considering graph classes which are closed under these transformations, computational complexity results that are valid for one of the problems give rise to results for the other. The question concerning the existence of a class where one of the problems is polynomial and the other NP-complete is still open.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 207-212
Journal: Electronic Notes in Discrete Mathematics - Volume 37, 1 August 2011, Pages 207-212