Search

The Hamiltonian cycle problem is one of the most important problems in graph theory that has many applications. This problem is NP-complete for general grid graphs. For solid grid graphs, there are polynomial-time algorithms. Existence of polynomial-time algorithms for grid graphs with few holes has been asked in the literature. In this paper, we give a linear-time algorithm for rectangular grid graphs with two rectangular holes. This extends the previous result for rectangular grid graphs with one rectangular hole. We first present the forbidden conditions in which there is no Hamiltonian cycle for any grid graphs, including rectangular grid graphs with rectangular holes. We then show that if these forbidden conditions do not hold, then there exists a Hamiltonian cycle. The proof is constructive, therefore, it gives an algorithm. An application of the problem is in off-line robot exploration. [ABSTRACT FROM AUTHOR]

The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L-shaped grid graph can be computed in linear time. [ABSTRACT FROM AUTHOR]

The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In addition, the results show that the problem is hard to approximate within any reasonable factor for general graphs. We introduce a polynomial-time-approximation algorithm for the longest path problem in solid grid graphs. Our algorithm can also approximate the longest path between any two given boundary vertices of a solid grid graph within the same approximation factor. [ABSTRACT FROM AUTHOR]