کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6896424 | 1445996 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum edge blocker dominating set problem
ترجمه فارسی عنوان
حداقل مسدود کننده لبه غالب مشکل مجموعه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r > 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r > 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 247, Issue 1, 16 November 2015, Pages 16-26
Journal: European Journal of Operational Research - Volume 247, Issue 1, 16 November 2015, Pages 16-26
نویسندگان
Foad Mahdavi Pajouh, Jose L. Walteros, Vladimir Boginski, Eduardo L. Pasiliao,