کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871854 | 681668 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Hamiltonian cycles in linear-convex supergrid graphs
ترجمه فارسی عنوان
سیکل همیلتون در نمودارهای خطی-محدب سوپر لایه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چرخه همیلتون محلی متصل شده نمودار ابررسانا خطی محدب، نمودار متعارف نمودار شبکه، نمودار شبکه مثلثی، چرخ خیاطی کامپیوتری،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A supergrid graph is a finite induced subgraph of the infinite graph associated with the two-dimensional supergrid. The supergrid graphs contain grid graphs and triangular grid graphs as subgraphs. The Hamiltonian cycle problem for grid and triangular grid graphs was known to be NP-complete. Recently, we have proved the Hamiltonian cycle problem on supergrid graphs to be NP-complete. The Hamiltonian cycle problem on supergrid graphs can be applied to control the stitching trace of computerized sewing machines. In this paper, we will study the Hamiltonian cycle property of linear-convex supergrid graphs which form a subclass of supergrid graphs. A connected graph is called k-connected if there are k vertex-disjoint paths between every pair of vertices, and is called locally connected if the neighbors of each vertex in it form a connected subgraph. In this paper, we first show that any 2-connected, linear-convex supergrid graph is locally connected. We then give constructive proofs to show that any 2-connected, linear-convex supergrid graph contains a Hamiltonian cycle. Based on the constructive proofs, we finally present a linear-time algorithm to construct a Hamiltonian cycle of a 2-connected, linear-convex supergrid graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 99-112
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 99-112
نویسندگان
Ruo-Wei Hung,