Not being (super)thin or solid is hard: A study of grid Hamiltonicity
Not being (super)thin or solid is hard: A study of grid Hamiltonicity
复制标题
DOI：
10.1016/j.comgeo.2008.11.004
复制
发表时间：
2009-08-01
影响因子：
0.6
通讯作者：
Xiao, Henry
中科院分区：
文献类型：
--
作者：
Arkin, Esther M.;Fekete, Sandor P.;Xiao, Henry
我们对网格的哈密顿性进行了系统的研究——网格是由具有全等正则凸多边形（三角形、正方形或六边形）的平面平铺的顶点的有限子集导出的图。总结并扩展了通常“方形”的现有分类。网格，我们给出了网格图的全面分类。对于许多类别的网格图，我们解决了哈密顿循环问题的计算复杂性。对于存在多项式时间算法的图，我们给出有效的算法来找到哈密顿循环。对于任何 g >= 6，我们还建立了平面二分最大度 3 图的哈密顿循环与周长 g 平面最大度 3 图的 C-g 类中的哈密顿循环之间的一一对应关系。作为对应关系的应用，我们表明对于 C-g 中的图，哈密顿循环问题是 NP 完全的，并且对于任何 N >= 5，Cg 中存在恰好具有 N 个哈密顿循环的图。我们还证明，对于 Cg 中的图，当 g > 16 时，中国邮差旅行给出了 TSR 的 (1 + 8/g) 近似，从而提高了 Christofides 比率。我们进一步证明，在任何图中，由 Christofides 算法获得的旅行都不比中国邮差旅行长。 (C) 2008 Elsevier B.V. 保留所有权利。
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". 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 g >= 6, a one-to-one correspondence between Hamiltonian cycles in planar bipartite maximum-degree-3 graphs and Hamiltonian cycles in the class C-g of girth-g planar maximum-degree-3 graphs. As applications of the correspondence, we show that for graphs in C-g the Hamiltonian cycle problem is NP-complete and that for any N >= 5 there exist graphs in Cg that have exactly N Hamiltonian cycles. We also prove that for the graphs in Cg, a Chinese Postman tour gives a (1 + 8/g)-approximation to TSR 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. (C) 2008 Elsevier B.V. All rights reserved.