MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

The Hardness of Finding Hamiltonian Cycle in Grids Graphs of Semiregular Tessellations

Kaiying Hou Phillips Academy

S.-T. Yau High School Science Awarded Papers mathscidoc:1801.35014

Yau Science Award (Math), 2017.12
The Hamiltonian cycle problem is an important problem in graph theory and computer science. It is a special case of the famous traveling salesman problem. A signi cant amount of research has been done on the special cases of nding Hamiltonian cycles in subgraphs of triangular, square and hexagonal grids. However, there is little work on more complicated grids. In this paper, we investigate the hardness of Hamiltonian cycle problem in grid graphs of semiregular tessellations, which are tessellations formed by two or more kinds of regular polygons. There are only eight semiregular tessellations, and we prove that the Hamiltonian cycle problem in all of them are NP-complete by reducing from NP-complete problems, such as the Hamiltonian cycle problem in max degree 3 bipartite planar graphs. Knowing the NP-completeness of Hamiltonian cycle problem in semiregular grids indicates that there will not be any polynomial time algorithm that solves the Hamiltonian path problem in these tessellations if NP does not equal to P, which helps show the limits of ecient motion planning algorithms and provides new information about what makes problems computationally dicult to solve.
No keywords uploaded!
[ Download ] [ 2018-01-13 19:54:52 uploaded by yauawardadmin ] [ 1165 downloads ] [ 0 comments ] 
@inproceedings{kaiying2017the,
  title={The Hardness of Finding Hamiltonian Cycle in Grids Graphs of Semiregular Tessellations},
  author={Kaiying Hou},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180113195452806524887},
  booktitle={Yau Science Award (Math)},
  year={2017},
}
Kaiying Hou. The Hardness of Finding Hamiltonian Cycle in Grids Graphs of Semiregular Tessellations. 2017. In Yau Science Award (Math). http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20180113195452806524887.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved