کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654477 1632845 2006 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the independent dominating set polytope
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the independent dominating set polytope
چکیده انگلیسی

In this paper, we consider the independent dominating set polytope. We give a complete linear description of that polytope when the graph is reduced to a cycle. This description uses a general class of valid inequalities introduced in [T.M. Contenza, Some results on the dominating set polytope, Ph.D. Dissertation, University of Kentucky, 2000]. We devise a polynomial time separation algorithm for these inequalities. As a consequence, we obtain a polynomial time cutting plane algorithm for the minimum (maximum) independent dominating set problem on a cycle. We also introduce a lifting operation called twin operation, and discuss some polyhedral consequences. In particular, we show that the above results can be extended to a more general class of graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 27, Issue 4, May 2006, Pages 601–616
نویسندگان
, ,