کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648969 | 1632434 | 2010 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Size-constrained graph partitioning polytopes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the equi-partition problem and the kk-way equi-partition problem. In this paper, we analyze the structure of the corresponding polytope and prove several results concerning the facial structure. Our analysis yields important results for the closely related equi-partition and kk-way equi-partition polytopes as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 24, 28 December 2010, Pages 3473–3493
Journal: Discrete Mathematics - Volume 310, Issue 24, 28 December 2010, Pages 3473–3493
نویسندگان
M. Labbé, F. Aykut Özsoy,