PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 57-69
Tytuł artykułu

When is an Incomplete 3 × n Latin Rectangle Completable?

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
33
Numer
1
Strony
57-69
Opis fizyczny
Daty
wydano
2013-03-01
online
2013-04-13
Twórcy
  • 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, Reinhardt.Euler@univ-brest.fr
  • AGH University of Science and Technology, Faculty of Geology, Geophysics and Environment Protection, Department of Geoinformatics and Applied Computer Science, 30-059 Cracow, Poland, oleksik@agh.edu.pl
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1648
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.