Título:
Tromino tilings with pegs via flow networks.
Otros títulos:
Coordinador:
Director:
Compilador:
Autor:
Akagi, Javier T.
Canale, Eduardo A.
Villagra, Marcos
Canale, Eduardo A.
Villagra, Marcos
Tutor:
Tipo de documento:
Preprint
Editor:
Palabras clave:
Tromino tilings
Linear-time reduction
Parsimonious reduction
Maximum-flow
Bipartite matchings
Linear-time reduction
Parsimonious reduction
Maximum-flow
Bipartite matchings
Descriptores:
Año de publicación:
2021
Contenido:
Resumen:
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.
Descripción:
metadata.articulos.dc.description.uri:
Editorial:
EN:
Financiadores:
Citación:
Akagi, J., Canale, E. y Villagra, M. Tromino tilings with pegs via flow networks [Preprint]. Publicado en: Procedia Computer Science, 2021, vol. 195, pp. 459-467. DOI: 10.1016/j.procs.2021.11.056.
Citación:
metadata.articulos.cc.license.name:
ISBN:
e-ISBN:
ISSN:
ISMN:
Otros identificadores:
Cobertura geográfica:
Cobertura temporal:
Departamento académico:
Grupo de investigación:
Licencia:
Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| ACV21.pdf | Preprint | 318.18 KB | Adobe PDF |