کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478650 | 1446118 | 2010 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Satisfactory graph partition, variants, and generalizations
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Satisfactory graph partition, variants, and generalizations Satisfactory graph partition, variants, and generalizations](/preview/png/478650.png)
چکیده انگلیسی
The Satisfactory Partition problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler, Algorithmic approach to the satisfactory graph partitioning problem, European Journal of Operational Research 125 (2000) 283–291] and studied further by other authors. In this paper we first review some applications and related problems. Then, we survey structural, complexity, and approximation results obtained for Satisfactory Partition and for some of its variants and generalizations. A list of open questions concludes this survey.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 206, Issue 2, 16 October 2010, Pages 271–280
Journal: European Journal of Operational Research - Volume 206, Issue 2, 16 October 2010, Pages 271–280
نویسندگان
Cristina Bazgan, Zsolt Tuza, Daniel Vanderpooten,