کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419707 | 683851 | 2009 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Counting feasible solutions of the traveling salesman problem with pickups and deliveries is #P#P-complete
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Deciding whether or not a feasible solution to the Traveling Salesman Problem with Pickups and Deliveries (TSPPD) exists is polynomially solvable. We prove that counting the number of feasible solutions of the TSPPD is hard by showing that the problem is #P#P-complete.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2541–2547
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2541–2547
نویسندگان
Gerardo Berbeglia, Geňa Hahn,