کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5128295 | 1378588 | 2016 | 24 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The minimum weakly connected independent set problem: Polyhedral results and Branch-and-Cut
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Let G=(V,E) be a connected graph. An independent set WâV is said to be weakly connected if the spanning subgraph GW=(V,δ(W)) is connected where δ(W) is the set of edges with exactly one end in W. We present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristic separation procedures. Finally, we develop a Branch-and-Cut algorithm and test it on two classes of graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 22, Part A, November 2016, Pages 87-110
Journal: Discrete Optimization - Volume 22, Part A, November 2016, Pages 87-110
نویسندگان
Fatiha Bendali, Jean Mailfert, Djelloul Mameri,