کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871897 681683 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An approximation algorithm for the longest cycle problem in solid grid graphs
ترجمه فارسی عنوان
یک الگوریتم تقریبی برای طولانی ترین چرخه در گراف های شبکه جامد
کلمات کلیدی
طولانی ترین چرخه، چرخه همیلتون الگوریتم تقریبی، نمودار شبکه جامد،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,