On the completability of incomplete Latin squares (Q966163)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the completability of incomplete Latin squares |
scientific article |
Statements
On the completability of incomplete Latin squares (English)
0 references
27 April 2010
0 references
An \textit{incomplete Latin square} is an \(n \times n\) array where some of the cells have an entry from \(\{1,\dots,n\}\) such that no symbol occurs twice in a row or column. The square is \textit{completable} if it can be extended to a Latin square of the same order. The question is {`Which incomplete Latin squares are completable?'} In this paper the authors examine when an incomplete Latin square has a row that can be completed. They introduce an availability matrix and use the Frobenius-König Theorem to find necessary and sufficient conditions for such a row. They then examine when the incomplete square has two rows that can be extended using the framework of \((1,2)\)-permutations. They consider an integer programming formulation with polyhedral results, and a nice application for class-teacher time-table problems.
0 references
incomplete Latin square
0 references
completabele Latin square
0 references
complete Latin square
0 references
integer programming
0 references
class teacher time table problem
0 references
0 references
0 references