کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872451 | 681651 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal ordering of independent tests with precedence constraints
ترجمه فارسی عنوان
ترتیب بهینه تست های مستقل با محدودیت های قضیه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تست سفارش، بهینه سازی محدود، پیچیدگی مشکلات مرتب سازی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Finding an optimal ordering is easy when the tests are completely independent. Introducing precedence constraints, we show that the optimization problem becomes NP-hard when the constraints are given by means of a general partial order. Restrictions of the constraints to non-trivial special cases that allow for low-order polynomial-time algorithms are examined.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 115-127
Journal: Discrete Applied Mathematics - Volume 162, 10 January 2014, Pages 115-127
نویسندگان
D. Berend, R. Brafman, S. Cohen, S.E. Shimony, S. Zucker,