When is an Incomplete 3 × n Latin Rectangle Completable?

• Autorzy: Reinhardt Euler , Paweł Oleksik
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

incomplete latin rectangle; completability; solution space enumeration; branch-and-bound

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 1
• Strony: 57-69

Daty

wydano

2013-03-01

online

2013-04-13

Twórcy

autor

Reinhardt Euler

• Université Européenne de Bretagne and Lab-STICC, CNRS, UMR 6285, Université de Brest, B.P.809, 20 Avenue Le Gorgeu, 29285 Brest Cedex, France

autor

Paweł Oleksik

• AGH University of Science and Technology, Faculty of Geology, Geophysics and Environment Protection, Department of Geoinformatics and Applied Computer Science, 30-059 Cracow, Poland

Bibliografia

• [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[Crossref]
• [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[Crossref]
• [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[Crossref]
• [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[Crossref][WoS]
• [8] T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958-961. doi:10.2307/2309221[Crossref]
• [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[WoS][Crossref]
• [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[Crossref]
• [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[WoS][Crossref]
• [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[Crossref]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1648