Not being (super)thin or solid is hard: A study of grid Hamiltonicity

详细信息    查看全文

• 作者：Esther M. Arkin ; Sá ; ndor P. Fekete ; Kamrul Islam ; Henk Meijer ; Joseph S.B. Mitchell ; Yurai Nú ; ñ ; ez-Rodrd ; guez ; Valentin Polishchuk ; David Rappaport ; Henry Xiao
• 关键词：Hamiltonian cycle ; Grid graph ; High-girth graph ; Covering tour
• 刊名：Computational Geometry
• 出版年：2009
• 出版时间：August 2009
• 年：2009
• 卷：42
• 期：6-7
• 页码：582-605
• 全文大小：2013 K

文摘

We give a systematic study of Hamiltonicity of grids — the graphs induced by finite subsets of vertices of the tilings of the plane with congruent regular convex polygons (triangles, squares, or hexagons). Summarizing and extending existing classification of the usual, “squareȁd;, grids, we give a comprehensive taxonomy of the grid graphs. For many classes of grid graphs we resolve the computational complexity of the Hamiltonian cycle problem. For graphs for which there exists a polynomial-time algorithm we give efficient algorithms to find a Hamiltonian cycle.

We also establish, for any g6, a one-to-one correspondence between Hamiltonian cycles in planar bipartite maximum-degree-3 graphs and Hamiltonian cycles in the class of girth-g planar maximum-degree-3 graphs. As applications of the correspondence, we show that for graphs in the Hamiltonian cycle problem is NP-complete and that for any N5 there exist graphs in that have exactly N Hamiltonian cycles. We also prove that for the graphs in , a Chinese Postman tour gives a -approximation to TSP, improving thereby the Christofides ratio when g>16. We show further that, in any graph, the tour obtained by Christofides' algorithm is not longer than a Chinese Postman tour.