演講公告

演講主題：Complexity of tiling with rectangles
主講人：Jed Yang 博士(University of Minnesota, U.S.A.)
演講日期：2013年12月31日(星期二) 下午1:00-2:00
演講地點：(光復校區) 科學一館223室
摘要內容：
Abstract.
Can a set of tiles (think polyominoes) tile a finite region? This decision problem is (computationally) hard in general. In the case of simply connected regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. In this talk, we will describe the construction of a set of rectangular tiles whose tileability problem is NP-complete for simply connected regions. If time permits, we will also discuss some tiling problems in the infinite setting.
相關檔案：Talk_1021231.doc

$返回$ go back