کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871897 | 681683 | 2016 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An approximation algorithm for the longest cycle problem in solid grid graphs
ترجمه فارسی عنوان
یک الگوریتم تقریبی برای طولانی ترین چرخه در گراف های شبکه جامد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طولانی ترین چرخه، چرخه همیلتون الگوریتم تقریبی، نمودار شبکه جامد،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2n3+1 in 2-connected n-node solid grid graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 6-12
Journal: Discrete Applied Mathematics - Volume 204, 11 May 2016, Pages 6-12
نویسندگان
Asghar Asgharian Sardroud, Alireza Bagheri,