کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652768 | 1632595 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We propose an integer programming formulation for the problem of finding the maximum k-partite induced sub-graph of a graph G based on representatives of stable sets. We investigate upper bounds provided by the solution, via a parallel sub-gradient algorithm, of a Lagrangian decomposition that breaks up this formulation into maximum weighted stable set problems for sub-graphs of G. Some computational experiments were carried out with an effective multi-threaded parallel implementation in a multi-core system, and their results are presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 503-510
Journal: Electronic Notes in Discrete Mathematics - Volume 36, 1 August 2010, Pages 503-510