کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951934 | 1441994 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Graph matching problems and the NP-hardness of sortedness constraints
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we formulate one of these problems as a marriage scheduling problem, which is a special perfect matching problem in a bipartite graph. We show that the marriage scheduling problem is NP-complete, and we explain the relationships between this graph problem and the sortedness constraints. As a consequence, we deduce that the sort(U,V) constraint (Older et al., 1995), the sort(U,V,P) constraint (Zhou, 1996) and the recently introduced keysorting(U,V,Keys,P) constraint (Carlsson et al., 2014) are intractable (assuming P â NP) for integer variables whose domains are not limited to intervals.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 16-27
Journal: Theoretical Computer Science - Volume 695, 26 September 2017, Pages 16-27
نویسندگان
Irena Rusu,