MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

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 ] [ 819 downloads ] [ 0 comments ] [ Cited by 12 ] 
@inproceedings{wen-qi2011approximating,
  title={Approximating the longest paths in grid graphs},
  author={Wen-Qi Zhang, and Yong-Jin Liu},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819152545835538265},
  booktitle={Theoretical Computer Science},
  volume={412},
  number={39},
  pages={5340},
  year={2011},
}
Wen-Qi Zhang, and Yong-Jin Liu. Approximating the longest paths in grid graphs. 2011. Vol. 412. In Theoretical Computer Science. pp.5340. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20160819152545835538265.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved