| Metadato | Etiqueta | Valor | Idioma |
|---|---|---|---|
| dc.contributor.author | Autor | Akagi, Javier T. | - |
| dc.contributor.author | Autor | Canale, Eduardo A. | - |
| dc.contributor.author | Autor | Villagra, Marcos | - |
| dc.contributor.filiacion | Filiación | Akagi Javier T., Universidad Nacional de Asunción, Paraguay | - |
| dc.contributor.filiacion | Filiación | Canale Eduardo A., Universidad de la República (Uruguay). Facultad de Ingeniería. | - |
| dc.contributor.filiacion | Filiación | Villagra Marcos, Universidad Nacional de Asunción, Paraguay | - |
| dc.date.accessioned | Fecha ingreso | 2025-07-09T17:20:31Z | - |
| dc.date.available | Fecha disponible | 2025-07-09T17:20:31Z | - |
| dc.date.issued | Año de publicación | 2021 | - |
| dc.description.abstract | 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. | es |
| dc.format.extent | Extensión | 9 p. | es |
| dc.format.mimetype | Formato | application/pdf | es |
| dc.identifier.citation | 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. | es |
| dc.identifier.uri | URI | https://hdl.handle.net/20.500.12008/50523 | - |
| dc.language.iso | Idioma | en | es |
| dc.rights | Derechos | Las obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014) | es |
| dc.rights.licence | Licencia | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) | es |
| dc.subject | Palabras clave | Tromino tilings | es |
| dc.subject | Palabras clave | Linear-time reduction | es |
| dc.subject | Palabras clave | Parsimonious reduction | es |
| dc.subject | Palabras clave | Maximum-flow | es |
| dc.subject | Palabras clave | Bipartite matchings | es |
| dc.title | Título | Tromino tilings with pegs via flow networks. | es |
| dc.type | Tipo de documento | Preprint | es |
Colecciones:
| Ficheros | Descripción | Tamaño | Formato | ||
|---|---|---|---|---|---|
| ACV21.pdf | Preprint | 318.18 KB | Adobe PDF |