Approximating the longest paths in grid graphs

Wen-Qi Zhang Tsinghua University Yong-Jin Liu Tsinghua University

Computational Geometry mathscidoc:1608.09010

Theoretical Computer Science, 412, (39), 5340, 2011.9
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 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.
Long paths, Square-free 2-factor, Grid graphs
[ Download ] [ 2016-08-19 15:25:45 uploaded by liuyj ] [ 703 downloads ] [ 0 comments ] [ Cited by 12 ]
  title={Approximating the longest paths in grid graphs},
  author={Wen-Qi Zhang, and Yong-Jin Liu},
  booktitle={Theoretical Computer Science},
Wen-Qi Zhang, and Yong-Jin Liu. Approximating the longest paths in grid graphs. 2011. Vol. 412. In Theoretical Computer Science. pp.5340.
Please log in for comment!
Contact us: | Copyright Reserved