کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874793 | 688209 | 2014 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new upper bound for the traveling salesman problem in cubic graphs
ترجمه فارسی عنوان
مرز جدیدی برای مشکل فروش فروشنده در نمودار مکعب است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های دقیق مشکل فروشنده مسافرتی نمودار مکعبی، چرخه همیلتون
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We provide a new upper bound for traveling salesman problem (TSP) in cubic graphs, i.e. graphs with maximum vertex degree three, and prove that the problem for an n-vertex graph can be solved in O(1.2553n) time and in linear space. We show that the exact TSP algorithm of Eppstein, with some minor modifications, yields the stated result. The previous best known upper bound O(1.251n) was claimed by Iwama and Nakashima [Proc. COCOON 2007]. Unfortunately, their analysis contains several mistakes that render the proof for the upper bound invalid.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 27, July 2014, Pages 1-20
Journal: Journal of Discrete Algorithms - Volume 27, July 2014, Pages 1-20
نویسندگان
Maciej LiÅkiewicz, Martin R. Schuster,