On completing latin squares (Q5951961)
From MaRDI portal
scientific article; zbMATH DE number 1687487
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On completing latin squares |
scientific article; zbMATH DE number 1687487 |
Statements
On completing latin squares (English)
0 references
19 June 2002
0 references
It is known that the problem of completing a partially filled latin square is NP-complete. In the paper under review, the authors prove that this problem remains NP-complete even with the additional assumption that no more than three unfilled cells occur in each row and column of the square and where only three integers are available.
0 references
latin squares
0 references
NP-complete problems
0 references
