1 |
Completing partial Latin squares with one filled row, column and symbolCasselgren, Carl Johan, Häggkvist, Roland January 2013 (has links)
Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. Assume further that s is the symbol of cell (r,c) in P. We prove that P is completable to a Latin square if n≥8 and n is divisible by 4, or n≤7 and n∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.
|
Page generated in 0.0667 seconds