Paper Info
Title
Domino Tatami Covering is NP-complete
Abstract
A covering with dominoes of a rectilinear region is called \emph{tatami} if no four dominoes meet at any point. We describe a reduction from planar 3SAT to Domino Tatami Covering. As a consequence it is NP-complete to decide whether there is a perfect matching of a graph that meets every 4-cycle, even if the graph is restricted to be an induced subgraph of the grid-graph. The gadgets used in the reduction were discovered with the help of a SAT-solver.
Year
DOI
Venue
2013
10.1007/978-3-642-45278-9_13
IWOCA
DocType
Volume
Citations 
Conference
abs/1305.6669
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Alejandro Erickson1145.84
Frank Ruskey2906116.61