期刊
DISCRETE APPLIED MATHEMATICS
卷 157, 期 3, 页码 464-475出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.dam.2008.05.026
关键词
Tiling polyominoes; Plane tesselation; Longest common extensions
On square or hexagonal lattices, tiles or polyominoes are coded by words. The polyominoes that tile the plane by translation are characterized by the Beauquier-Nivat condition. By using the constant time algorithms for computing the longest common extensions in two words, we provide a linear time algorithm in the case of pseudo-square polyominoes, improving the previous quadratic algorithm of Gambini and Vuillon. We also have a linear algorithm for pseudo-hexagon polyominoes not containing arbitrarily large square factors. The results are extended to more general tiles. (c) 2008 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据