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.0012 seconds