Tromino Tilings with Pegs via Flow Networks Article Swipe
Javier T. Akagi
,
Eduardo Canale
,
Marcos Villagra
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.1016/j.procs.2021.11.056
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.1016/j.procs.2021.11.056
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.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://doi.org/10.1016/j.procs.2021.11.056
- OA Status
- diamond
- References
- 7
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W3044246926
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3044246926Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1016/j.procs.2021.11.056Digital Object Identifier
- Title
-
Tromino Tilings with Pegs via Flow NetworksWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-01-01Full publication date if available
- Authors
-
Javier T. Akagi, Eduardo Canale, Marcos VillagraList of authors in order
- Landing page
-
https://doi.org/10.1016/j.procs.2021.11.056Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
diamondOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.1016/j.procs.2021.11.056Direct OA link when available
- Concepts
-
Mathematics, Combinatorics, Mathematical proof, Square tiling, Lattice (music), Grid, Geometry, Physics, AcousticsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
7Number of works referenced by this work
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3044246926 |
|---|---|
| doi | https://doi.org/10.1016/j.procs.2021.11.056 |
| ids.doi | https://doi.org/10.48550/arxiv.2007.12651 |
| ids.mag | 3044246926 |
| ids.openalex | https://openalex.org/W3044246926 |
| fwci | 0.0 |
| type | preprint |
| title | Tromino Tilings with Pegs via Flow Networks |
| biblio.issue | |
| biblio.volume | 195 |
| biblio.last_page | 467 |
| biblio.first_page | 459 |
| topics[0].id | https://openalex.org/T14339 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9983000159263611 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Image Processing and 3D Reconstruction |
| topics[1].id | https://openalex.org/T12162 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9936000108718872 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1703 |
| topics[1].subfield.display_name | Computational Theory and Mathematics |
| topics[1].display_name | Cellular Automata and Applications |
| topics[2].id | https://openalex.org/T10996 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9847000241279602 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1704 |
| topics[2].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[2].display_name | Computational Geometry and Mesh Generation |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C33923547 |
| concepts[0].level | 0 |
| concepts[0].score | 0.640311062335968 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[0].display_name | Mathematics |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6383270621299744 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C108710211 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6089061498641968 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q11538 |
| concepts[2].display_name | Mathematical proof |
| concepts[3].id | https://openalex.org/C178650486 |
| concepts[3].level | 3 |
| concepts[3].score | 0.4882400333881378 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q1128619 |
| concepts[3].display_name | Square tiling |
| concepts[4].id | https://openalex.org/C2781204021 |
| concepts[4].level | 2 |
| concepts[4].score | 0.43332189321517944 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q6497091 |
| concepts[4].display_name | Lattice (music) |
| concepts[5].id | https://openalex.org/C187691185 |
| concepts[5].level | 2 |
| concepts[5].score | 0.19312378764152527 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q2020720 |
| concepts[5].display_name | Grid |
| concepts[6].id | https://openalex.org/C2524010 |
| concepts[6].level | 1 |
| concepts[6].score | 0.1724012792110443 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[6].display_name | Geometry |
| concepts[7].id | https://openalex.org/C121332964 |
| concepts[7].level | 0 |
| concepts[7].score | 0.06725504994392395 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[7].display_name | Physics |
| concepts[8].id | https://openalex.org/C24890656 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q82811 |
| concepts[8].display_name | Acoustics |
| keywords[0].id | https://openalex.org/keywords/mathematics |
| keywords[0].score | 0.640311062335968 |
| keywords[0].display_name | Mathematics |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.6383270621299744 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/mathematical-proof |
| keywords[2].score | 0.6089061498641968 |
| keywords[2].display_name | Mathematical proof |
| keywords[3].id | https://openalex.org/keywords/square-tiling |
| keywords[3].score | 0.4882400333881378 |
| keywords[3].display_name | Square tiling |
| keywords[4].id | https://openalex.org/keywords/lattice |
| keywords[4].score | 0.43332189321517944 |
| keywords[4].display_name | Lattice (music) |
| keywords[5].id | https://openalex.org/keywords/grid |
| keywords[5].score | 0.19312378764152527 |
| keywords[5].display_name | Grid |
| keywords[6].id | https://openalex.org/keywords/geometry |
| keywords[6].score | 0.1724012792110443 |
| keywords[6].display_name | Geometry |
| keywords[7].id | https://openalex.org/keywords/physics |
| keywords[7].score | 0.06725504994392395 |
| keywords[7].display_name | Physics |
| language | en |
| locations[0].id | doi:10.1016/j.procs.2021.11.056 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S120348307 |
| locations[0].source.issn | 1877-0509 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | 1877-0509 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Procedia Computer Science |
| locations[0].source.host_organization | https://openalex.org/P4310320990 |
| locations[0].source.host_organization_name | Elsevier BV |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320990 |
| locations[0].source.host_organization_lineage_names | Elsevier BV |
| locations[0].license | cc-by-nc-nd |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by-nc-nd |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Procedia Computer Science |
| locations[0].landing_page_url | https://doi.org/10.1016/j.procs.2021.11.056 |
| locations[1].id | pmh:oai:arXiv.org:2007.12651 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | https://arxiv.org/pdf/2007.12651 |
| locations[1].version | submittedVersion |
| locations[1].raw_type | text |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://arxiv.org/abs/2007.12651 |
| locations[2].id | mag:3044246926 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | |
| locations[2].pdf_url | |
| locations[2].version | submittedVersion |
| locations[2].raw_type | |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | arXiv (Cornell University) |
| locations[2].landing_page_url | http://arxiv.org/pdf/2007.12651.pdf |
| locations[3].id | doi:10.48550/arxiv.2007.12651 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S4306400194 |
| locations[3].source.issn | |
| locations[3].source.type | repository |
| locations[3].source.is_oa | True |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | arXiv (Cornell University) |
| locations[3].source.host_organization | https://openalex.org/I205783295 |
| locations[3].source.host_organization_name | Cornell University |
| locations[3].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[3].license | |
| locations[3].pdf_url | |
| locations[3].version | |
| locations[3].raw_type | article |
| locations[3].license_id | |
| locations[3].is_accepted | False |
| locations[3].is_published | |
| locations[3].raw_source_name | |
| locations[3].landing_page_url | https://doi.org/10.48550/arxiv.2007.12651 |
| indexed_in | arxiv, crossref, datacite |
| authorships[0].author.id | https://openalex.org/A5066161822 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-8169-5654 |
| authorships[0].author.display_name | Javier T. Akagi |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Javier T. Akagi |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5085419342 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-1311-6497 |
| authorships[1].author.display_name | Eduardo Canale |
| authorships[1].countries | UY |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I180910786 |
| authorships[1].affiliations[0].raw_affiliation_string | University of the Republic, Uruguay#TAB# |
| authorships[1].institutions[0].id | https://openalex.org/I180910786 |
| authorships[1].institutions[0].ror | https://ror.org/030bbe882 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I180910786 |
| authorships[1].institutions[0].country_code | UY |
| authorships[1].institutions[0].display_name | Universidad de la República de Uruguay |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Eduardo A. Canale |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | University of the Republic, Uruguay#TAB# |
| authorships[2].author.id | https://openalex.org/A5076869132 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6081-9099 |
| authorships[2].author.display_name | Marcos Villagra |
| authorships[2].countries | PY |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I8379220 |
| authorships[2].affiliations[0].raw_affiliation_string | Universidad Nacional de Asunción |
| authorships[2].institutions[0].id | https://openalex.org/I8379220 |
| authorships[2].institutions[0].ror | https://ror.org/03f27y887 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I8379220 |
| authorships[2].institutions[0].country_code | PY |
| authorships[2].institutions[0].display_name | Universidad Nacional de Asunción |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Marcos Villagra |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Universidad Nacional de Asunción |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.1016/j.procs.2021.11.056 |
| open_access.oa_status | diamond |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Tromino Tilings with Pegs via Flow Networks |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T14339 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9983000159263611 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Image Processing and 3D Reconstruction |
| related_works | https://openalex.org/W3195881359, https://openalex.org/W3123325926, https://openalex.org/W2554519644, https://openalex.org/W2018748348, https://openalex.org/W2165725835, https://openalex.org/W2031578721, https://openalex.org/W2591316216, https://openalex.org/W2080896750, https://openalex.org/W2595753595, https://openalex.org/W1594327202, https://openalex.org/W118123718, https://openalex.org/W2116370612, https://openalex.org/W1977537695, https://openalex.org/W3045371194, https://openalex.org/W2556479273, https://openalex.org/W165065261, https://openalex.org/W2059295538, https://openalex.org/W2127519911, https://openalex.org/W3037410039, https://openalex.org/W2464795279 |
| cited_by_count | 0 |
| locations_count | 4 |
| best_oa_location.id | doi:10.1016/j.procs.2021.11.056 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S120348307 |
| best_oa_location.source.issn | 1877-0509 |
| best_oa_location.source.type | journal |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | 1877-0509 |
| best_oa_location.source.is_core | True |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | Procedia Computer Science |
| best_oa_location.source.host_organization | https://openalex.org/P4310320990 |
| best_oa_location.source.host_organization_name | Elsevier BV |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320990 |
| best_oa_location.source.host_organization_lineage_names | Elsevier BV |
| best_oa_location.license | cc-by-nc-nd |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | journal-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by-nc-nd |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Procedia Computer Science |
| best_oa_location.landing_page_url | https://doi.org/10.1016/j.procs.2021.11.056 |
| primary_location.id | doi:10.1016/j.procs.2021.11.056 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S120348307 |
| primary_location.source.issn | 1877-0509 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | 1877-0509 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Procedia Computer Science |
| primary_location.source.host_organization | https://openalex.org/P4310320990 |
| primary_location.source.host_organization_name | Elsevier BV |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320990 |
| primary_location.source.host_organization_lineage_names | Elsevier BV |
| primary_location.license | cc-by-nc-nd |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by-nc-nd |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Procedia Computer Science |
| primary_location.landing_page_url | https://doi.org/10.1016/j.procs.2021.11.056 |
| publication_date | 2021-01-01 |
| publication_year | 2021 |
| referenced_works | https://openalex.org/W2763985444, https://openalex.org/W2154815812, https://openalex.org/W1992101337, https://openalex.org/W2030077996, https://openalex.org/W1965407967, https://openalex.org/W2595753595, https://openalex.org/W2007385106 |
| referenced_works_count | 7 |
| abstract_inverted_index.A | 0 |
| abstract_inverted_index.a | 5, 12, 26, 44, 65, 79, 96, 134 |
| abstract_inverted_index.In | 39 |
| abstract_inverted_index.L. | 38 |
| abstract_inverted_index.We | 77 |
| abstract_inverted_index.an | 37 |
| abstract_inverted_index.be | 70, 113, 127 |
| abstract_inverted_index.in | 115, 138 |
| abstract_inverted_index.is | 4 |
| abstract_inverted_index.of | 14, 28, 36, 47, 55, 74, 81, 109, 119, 133 |
| abstract_inverted_index.on | 72 |
| abstract_inverted_index.to | 21, 100, 129 |
| abstract_inverted_index.we | 9, 19, 42 |
| abstract_inverted_index.(i) | 93 |
| abstract_inverted_index.The | 117 |
| abstract_inverted_index.and | 18, 60, 90, 104 |
| abstract_inverted_index.are | 10 |
| abstract_inverted_index.can | 68, 112, 125 |
| abstract_inverted_index.the | 29, 34, 48, 56, 75, 101, 107, 131 |
| abstract_inverted_index.top | 73 |
| abstract_inverted_index.(ii) | 105 |
| abstract_inverted_index.both | 120 |
| abstract_inverted_index.done | 114 |
| abstract_inverted_index.each | 61 |
| abstract_inverted_index.flow | 88 |
| abstract_inverted_index.have | 58 |
| abstract_inverted_index.hole | 66 |
| abstract_inverted_index.only | 69 |
| abstract_inverted_index.pegs | 59, 86, 137 |
| abstract_inverted_index.show | 91 |
| abstract_inverted_index.some | 53 |
| abstract_inverted_index.such | 110 |
| abstract_inverted_index.that | 67, 92, 124 |
| abstract_inverted_index.then | 126 |
| abstract_inverted_index.this | 40, 82 |
| abstract_inverted_index.used | 128 |
| abstract_inverted_index.want | 20 |
| abstract_inverted_index.with | 33, 64, 85, 136 |
| abstract_inverted_index.work | 41 |
| abstract_inverted_index.comes | 63 |
| abstract_inverted_index.given | 11 |
| abstract_inverted_index.pegs. | 76 |
| abstract_inverted_index.shape | 35 |
| abstract_inverted_index.study | 43 |
| abstract_inverted_index.there | 24, 94 |
| abstract_inverted_index.time. | 140 |
| abstract_inverted_index.using | 31, 87 |
| abstract_inverted_index.where | 8, 52 |
| abstract_inverted_index.$O(n)$ | 139 |
| abstract_inverted_index.decide | 22, 130 |
| abstract_inverted_index.exists | 25, 95 |
| abstract_inverted_index.number | 108 |
| abstract_inverted_index.placed | 71 |
| abstract_inverted_index.proofs | 118 |
| abstract_inverted_index.puzzle | 7 |
| abstract_inverted_index.region | 13, 30, 57, 135 |
| abstract_inverted_index.slight | 45 |
| abstract_inverted_index.tiling | 2, 27, 50, 83, 132 |
| abstract_inverted_index.contain | 122 |
| abstract_inverted_index.lattice | 16 |
| abstract_inverted_index.packing | 6 |
| abstract_inverted_index.present | 78 |
| abstract_inverted_index.problem | 3, 51, 84 |
| abstract_inverted_index.results | 121 |
| abstract_inverted_index.squares | 17 |
| abstract_inverted_index.tilings | 111 |
| abstract_inverted_index.tromino | 1, 49, 62 |
| abstract_inverted_index.whether | 23 |
| abstract_inverted_index.counting | 106 |
| abstract_inverted_index.networks | 89 |
| abstract_inverted_index.problem, | 103 |
| abstract_inverted_index.connected | 15 |
| abstract_inverted_index.positions | 54 |
| abstract_inverted_index.reduction | 99 |
| abstract_inverted_index.trominoes | 32 |
| abstract_inverted_index.variation | 46 |
| abstract_inverted_index.algorithms | 123 |
| abstract_inverted_index.linear-time | 97 |
| abstract_inverted_index.linear-time. | 116 |
| abstract_inverted_index.maximum-flow | 102 |
| abstract_inverted_index.parsimonious | 98 |
| abstract_inverted_index.characterization | 80 |
| cited_by_percentile_year | |
| countries_distinct_count | 2 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile.value | 0.00421869 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |