When is an Incomplete 3 × n Latin Rectangle Completable?

Reinhardt Euler; Paweł Oleksik

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 1, page 57-69
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Reinhardt Euler, and Paweł Oleksik. "When is an Incomplete 3 × n Latin Rectangle Completable?." Discussiones Mathematicae Graph Theory 33.1 (2013): 57-69. <http://eudml.org/doc/267599>.

@article{ReinhardtEuler2013,
abstract = {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.},
author = {Reinhardt Euler, Paweł Oleksik},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {incomplete latin rectangle; completability; solution space enumeration; branch-and-bound; incomplete Latin rectangle},
language = {eng},
number = {1},
pages = {57-69},
title = {When is an Incomplete 3 × n Latin Rectangle Completable?},
url = {http://eudml.org/doc/267599},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Reinhardt Euler
AU - Paweł Oleksik
TI - When is an Incomplete 3 × n Latin Rectangle Completable?
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 57
EP - 69
AB - 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.
LA - eng
KW - incomplete latin rectangle; completability; solution space enumeration; branch-and-bound; incomplete Latin rectangle
UR - http://eudml.org/doc/267599
ER -

References

top
  1. [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. Zbl1181.05018
  2. [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. [3] L. Brankovic, P. Horák, M. Miller and A. Rosa, Premature partial latin squares, Ars Combin. 63 (2002), 175-184. Zbl1071.05016
  4. [4] R. Burkard, M. Dell’Amico and S. Martello, Assignment Problems (SIAM, 2009). 
  5. [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] Zbl0538.05013
  6. [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] Zbl0614.05015
  7. [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] Zbl1201.05016
  8. [8] T. Evans, Embedding incomplete latin squares, Amer. Math. Monthly 67 (1960) 958-961. doi:10.2307/2309221[Crossref] 
  9. [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] Zbl1177.05116
  10. [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] Zbl0060.02801
  11. [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] Zbl1185.68838
  12. [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] Zbl0043.01202
  13. [13] B. Smetaniuk, A new construction on latin squares - I: A proof of the Evans Conjecture, Ars Combin. 11 (1981) 155-172. Zbl0471.05013
  14. [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. Zbl1029.90036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.