PDF
Discussiones Mathematicae Graph Theory 33(1) (2013)
57-69
DOI: https://doi.org/10.7151/dmgt.1648
Dedicated to Mieczysław Borowiecki on his 70th birthday
When Is an Incomplete 3× n Latin Rectangle Completable?
| Reinhardt Euler
Université Européenne de Bretagne and Lab-STICC, CNRS, UMR 6285, | Paweł Oleksik
AGH University of Science and Technology, |
Abstract
We use the concept of an availability matrix, introduced in Euler [7], to describe the family of all minimal incomplete 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
2010 Mathematics Subject Classification: 05B15, 05C65.
References
| [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. |
Received 24 March 2012
Revised 26 July 2012
Accepted 27 July 2012
Close