Geodesic
When is an Incomplete 3 × n Latin Rectangle Completable?
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 57-69.

Voir la notice de l'article provenant de la source Library of Science

We use the concept of an availability matrix, introduced in Euler [7], to describe the family of all minimal incomplete 3 × n latin rectangles that are not completable. We also present a complete description of minimal incomplete such latin squares of order 4.
Keywords: incomplete latin rectangle, completability, solution space enumeration, branch-and-bound 
@article{DMGT_2013_33_1_a5,
     author = {Euler, Reinhardt and Oleksik, Pawe{\l}},
     title = {When is an {Incomplete} 3 {\texttimes} n {Latin} {Rectangle} {Completable?}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {57--69},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a5/}
}
TY  - JOUR
AU  - Euler, Reinhardt
AU  - Oleksik, Paweł
TI  - When is an Incomplete 3 × n Latin Rectangle Completable?
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 57
EP  - 69
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a5/
LA  - en
ID  - DMGT_2013_33_1_a5
ER  - 
%0 Journal Article
%A Euler, Reinhardt
%A Oleksik, Paweł
%T When is an Incomplete 3 × n Latin Rectangle Completable?
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 57-69
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a5/
%G en
%F DMGT_2013_33_1_a5
Euler, Reinhardt; Oleksik, Paweł. When is an Incomplete 3 × n Latin Rectangle Completable?. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 1, pp. 57-69. http://geodesic.mathdoc.fr/item/DMGT_2013_33_1_a5/

[1] P. Adams, D. Bryant and M. Buchanan, Completing partial latin squares with two filled rows and two filled columns, Electron. J. Combin. 15 (2008) #R56.

[2] L.D. Andersen and A.J.W. Hilton, Thank Evans!, Proc. Lond. Math. Soc. (3) 47 (1983) 507-522. doi:10.1112/plms/s3-47.3.507

[3] L. Brankovic, P. Horák, M. Miller and A. Rosa, Premature partial latin squares, Ars Combin. 63 (2002), 175-184.

[4] R. Burkard, M. Dell’Amico and S. Martello, Assignment Problems (SIAM, 2009).

[5] C. Colbourn, The complexity of completing partial latin squares, Discrete Appl. Math. 8 (1984) 25-30. doi:10.1016/0166-218X(84)90075-1

[6] R. Euler, R.E. Burkard and R. Grommes, On latin squares and the facial structure of related polytopes, Discrete Math. 62 (1986) 155-181. doi:10.1016/0012-365X(86)90116-0

[7] R. Euler, On the completability of incomplete latin squares, European J. Combin. 31 (2010) 535-552. doi:10.1016/j.ejc.2009.03.036

[8] T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958-961. doi:10.2307/2309221

[9] M. Hagen, Lower bounds for three algorithms for transversal hypergraph generation, Discrete Appl. Math. 157 (2009) 1460-1469. doi:10.1016/j.dam.2008.10.004

[10] M. Hall, An existence theorem for latin squares, Bull. Amer. Math. Soc. 51 (1945) 387-388. doi:10.1090/S0002-9904-1945-08361-X

[11] L. Khachiyan, E. Boros, K. Elbassioni and V. Gurvich, A global parallel algorithm for the hypergraph transversal problem, Inform. Process. Lett. 101 (2007) 148-155. doi:10.1016/j.ipl.2006.09.006

[12] H.J. Ryser, A combinatorial theorem with an application to latin rectangles, Proc. Amer. Math. Soc. 2 (1951) 550-552. doi:10.1090/S0002-9939-1951-0042361-0

[13] B. Smetaniuk, A new construction on latin squares - I: A proof of the Evans Conjecture, Ars Combin. 11 (1981) 155-172.

[14] F.C.R. Spieksma, Multi-index assignment problems: complexity, approximation, applications, in: Nonlinear Assignment Problems, Algorithms and Applications, L. Pitsoulis and P. Pardalos, (Eds.), Kluwer (2000) 1-12.