Geodesic
The complexity of constructing gerechte designs
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/104
Classification : 05B15, 68Q17
Mots-clés : grechte designs, latin squares, partition of the cells of array 
@article{10_37236_104,
     author = {E. R. Vaughan},
     title = {The complexity of constructing gerechte designs},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/104},
     zbl = {1159.05010},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/104/}
}
TY  - JOUR
AU  - E. R. Vaughan
TI  - The complexity of constructing gerechte designs
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/104/
DO  - 10.37236/104
ID  - 10_37236_104
ER  - 
%0 Journal Article
%A E. R. Vaughan
%T The complexity of constructing gerechte designs
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/104/
%R 10.37236/104
%F 10_37236_104
E. R. Vaughan. The complexity of constructing gerechte designs. The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/104

Cité par Sources :