Databases
StackOverflow2013
Postsdbo
POGeneralizing the algorithm for domino tiling?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGeneralizing the algorithm for domino tiling?
    text
    copied!<p>In <strong><a href="https://stackoverflow.com/questions/4780201/maximum-number-of-dominoes-can-be-placed-inside-a-figure">this earlier question</a></strong> the OP asked the following problem:</p> <blockquote> <p>Given a rectangular grid where some squares are empty and some are filled, what is the largest number of 2x1 dominoes that can be placed into the world such that no two dominos overlap and no domino is atop a filled square?</p> </blockquote> <p>The (quite beautiful!) answer to this problem recognized that this is equivalent to finding a maximum bipartite matching in a specially-constructed graph. In this graph, each empty square has a node that is linked to each of its neighbors by an edge. Each domino then corresponds to an edge in the graph such that its endpoints are not covered by any other edge. Consequently, any set of edges that don't share a vertex (a matching) corresponds to an arrangement of dominoes, and vice-versa.</p> <p>My question is a generalization of this earlier one:</p> <blockquote> <p>Given a rectangular grid where some squares are empty and some are filled, what is the largest number of M x N dominoes (for a given M and N) that can be placed into the world such that no two dominos overlap and no domino is atop a filled square?</p> </blockquote> <p>I cannot see how to convert this into a matching problem as was done in the previous case. However, I also don't see any particular reason why this problem would immediately be NP-hard, so there may be a polynomial time solution to the problem.</p> <p>Is there an efficient algorithm for solving this problem? Or does anyone have a reduction that would show that this problem is NP-hard?</p> <p>Thanks so much!</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload