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.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:liu-92689 |
| Date | January 2013 |
| Creators | Casselgren, Carl Johan, Häggkvist, Roland |
| Publisher | Linköpings universitet, Matematik och tillämpad matematik, Linköpings universitet, Tekniska högskolan, Department of Mathematics, Umeå University, Sweden, Elsevier |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Article in journal, info:eu-repo/semantics/article, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Discrete Mathematics, 0012-365X, 2013, 313:9, s. 1011-1017 |
Page generated in 0.0019 seconds