کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5128295 1378588 2016 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The minimum weakly connected independent set problem: Polyhedral results and Branch-and-Cut
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
The minimum weakly connected independent set problem: Polyhedral results and Branch-and-Cut
چکیده انگلیسی

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
نویسندگان
, , ,