کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871168 | 1440179 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple cubic graphs with no short traveling salesman tour
ترجمه فارسی عنوان
نمودارهای مکعبی ساده بدون تور مسافرتی مسافر کوتاه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل فروشنده مسافرتی گراف مکعبی، گراف دو طرفه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let tsp(G) denote the length of a shortest traveling salesman tour in a graph G. We prove that for any ε>0, there exists a simple 2-connected planar cubic graph G1 such that tsp(G1)â¥(1.25âε)â
|V(G1)|, a simple 2-connected bipartite cubic graph G2 such that tsp(G2)â¥(1.2âε)â
|V(G2)|, and a simple 3-connected cubic graph G3 such that tsp(G3)â¥(1.125âε)â
|V(G3)|.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 218-222
Journal: Discrete Applied Mathematics - Volume 244, 31 July 2018, Pages 218-222
نویسندگان
Robert LukoÅ¥ka, Ján Mazák,