کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419015 | 681732 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the facets of lift-and-project relaxations under graph operations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovász and Schrijver (1991) [6] in the context of the stable set problem on graphs. Following the work of Wolsey (1976) [10], Lipták and Lovász (2001) [4] and Lipták and Tunçel (2003) [5], we investigate how to generate facets of the relaxations obtained by these procedures from facets of the relaxations of the original graph, after applying fundamental graph operations. We show our findings for the odd and the star subdivision, the stretching of a node and a new operation defined herein called the clique subdivision of an edge.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 164, Part 2, 19 February 2014, Pages 360–372
Journal: Discrete Applied Mathematics - Volume 164, Part 2, 19 February 2014, Pages 360–372
نویسندگان
Néstor E. Aguilera, Mariana S. Escalante, Pablo G. Fekete,