کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437616 | 690164 | 2015 | 17 صفحه PDF | دانلود رایگان |
In this paper, we first introduce a novel class of graphs, namely supergrid. Supergrid graphs include grid graphs and triangular grid graphs as their subgraphs. The Hamiltonian cycle and path problems for grid graphs and triangular grid graphs were known to be NP-complete. However, they are unknown for supergrid graphs. The Hamiltonian cycle (path) problem on supergrid graphs can be applied to control the stitching traces of computerized sewing machines. In this paper, we will prove that the Hamiltonian cycle problem for supergrid graphs is NP-complete. It is easily derived from the Hamiltonian cycle result that the Hamiltonian path problem on supergrid graphs is also NP-complete. We then show that two subclasses of supergrid graphs, including rectangular (parallelism) and alphabet, always contain Hamiltonian cycles.
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 132–148