کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13430722 | 1842451 | 2019 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On total f-domination: Polyhedral and algorithmic results
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a graph G=(V,E)
and integer values fv, vâV, a node subset DâV is a total f-dominating set if every node vâV is adjacent to at least fv nodes of D. Given a weight system c(v), vâV, the minimum weight total f-dominating set problem is to find a total f-dominating set of minimum total weight. In this article, we propose a polyhedral study of the associated polytope together with a complete and compact description of the polytope for totally unimodular graphs and cycles. We also propose a linear time dynamic programming algorithm for the case of trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 258, 15 April 2019, Pages 97-104
Journal: Discrete Applied Mathematics - Volume 258, 15 April 2019, Pages 97-104
نویسندگان
Mauro Dell'Amico, José Neto,