05955892

j

05955892 Zhang, Wen-Qi Liu, Yong-Jin Approximating the longest paths in grid graphs. Theor. Comput. Sci. 412, No. 39, 5340-5350 (2011). 2011 Elsevier Science Publishers, Amsterdam EN long paths square-free 2-factor grid graphs approximation algorithm

doi:10.1016/j.tcs.2011.06.010

Summary: We consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By analyzing several characteristics of four types of cross cells and presenting three cycle-merging operations and one extension operation, we propose an algorithm that finds in an $n$-vertex grid graph $G$, a long path of length at least $\frac56 n+2$. Our approximation algorithm runs in quadratic time. In addition to its theoretical value, our work has also an interesting application in image-guided maze generation.