科研之友
微信
新浪微博
Facebook
分享链接
摘要
A grid graph is a finite vertex-induced subgraph of the two-dimensional integer grid . A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.
- 出版日期2017-9
