The complexity of constructing gerechte designs (Q1010920)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The complexity of constructing gerechte designs
scientific article

    Statements

    The complexity of constructing gerechte designs (English)
    0 references
    7 April 2009
    0 references
    Summary: Gerechte designs are a specialisation of latin squares. A gerechte design is an \(n\times n\) array containing the symbols \(\{1,\dots,n\}\), together with a partition of the cells of the array into \(n\) regions of \(n\) cells each. The entries in the cells are required to be such that each row, column and region contains each symbol exactly once. We show that the problem of deciding if a gerechte design exists for a given partition of the cells is NP-complete. It follows that there is no polynomial time algorithm for finding gerechte designs with specified partitions unless P=NP.
    0 references
    grechte designs
    0 references
    latin squares
    0 references
    partition of the cells of array
    0 references
    0 references

    Identifiers