Yong-Jin Liu

Yong-Jin Liu

Yong-Jin Liu is a tenured Full Professor with the Computer Science Department at Tsinghua University. He obtained his Ph.D. degree in 2004 from Hong Kong University of Science & Technology. His research interests include computational geometry, computer graphics, computer aided design and pattern analysis.

Approximating the longest paths in grid graphs

Published in Theoretical Computer Science, 2011

Abstract: In this paper, we consider the problem of approximating the longest path in a grid graph that possesses a square-free 2-factor. By (1) analyzing several characteristics of four types of cross cells and (2) 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 $\frac{5}{6} 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.

Download paper here

More information

Recommended citation: Wen-Qi Zhang, Yong-Jin Liu* (2011) Approximating the longest paths in grid graphs. Theoretical Computer Science, Vol. 412, No. 39, pp. 5340-5350, 2011.