Hard and Easy Instances of L-Tromino Tilings
Javier Tadashi Akagi (National University of AsunciĆ³n, San Lorenzo, Paraguay)
13-Oct-2020, 17:15-17:45 (4 years ago)
Abstract: We study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm.
computational geometrydiscrete mathematicscombinatorics
Audience: researchers in the topic
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
Organizers: | Igor Pak*, Greta Panova |
*contact for this listing |
Export talk to