论文标题
通过流网络带钉钉的tromino斜利
Tromino Tilings with Pegs via Flow Networks
论文作者
论文摘要
一个tromino瓷砖问题是一个包装难题，我们得到了一个连接的晶格平方的区域，我们想决定是否存在使用具有L的形状的trominoes的区域的瓷砖。在这项工作中，我们研究了Tromino瓷砖问题的略有变化，使该区域的某些位置在每个Tromino中都有一个钉子，并且只能将一个孔放在PEG上。我们提出了使用流网络对PEG的这个瓷砖问题的表征，并表明（i）存在线性时间的简约减少对最大流量问题的简约减少，并且（ii）计算可以在线性时间内完成此类瓷砖的数量。两种结果的证明都包含算法，然后可以用这些算法来决定用$ o（n）$时间钉钉的区域的平铺。
A tromino tiling problem is a packing puzzle where we are given a region of connected lattice squares and we want to decide whether there exists a tiling of the region using trominoes with the shape of an L. In this work we study a slight variation of the tromino tiling problem where some positions of the region have pegs and each tromino comes with a hole that can only be placed on top of the pegs. We present a characterization of this tiling problem with pegs using flow networks and show that (i) there exists a linear-time parsimonious reduction to the maximum-flow problem, and (ii) counting the number of such tilings can be done in linear-time. The proofs of both results contain algorithms that can then be used to decide the tiling of a region with pegs in $O(n)$ time.
