کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871168 1440179 2018 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Simple cubic graphs with no short traveling salesman tour
ترجمه فارسی عنوان
نمودارهای مکعبی ساده بدون تور مسافرتی مسافر کوتاه
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,