Palabras clave
simulated annealing
football pool problem
combinatorics
Dominación de grafos
recocido simulado
problema de las apuestas en fútbol
combinatoria
Cómo citar
Resumen
En este artículo se describe el problema de la dominación de los grafos del tipo Znp y mezclas del tipo Zn3×Zm2 a través de subconjuntos dominantes de vértices de tamaño mínimo. Se introduce un algoritmo del tipo de recocido simulado para calcular cotas superiores de la cardinalidad de estos subconjuntos dominantes minimales.
Se demuestra la eficiencia del algoritmo al comparar los resultados obtenidos con los ya conocidos correspondientes a algunas clases de grafos, entre ellos los llamados grafos del “football pool problem”. Se establecen cotas superiores en algunos de los grafos del tipo Znp, con p ≥ 4. Los códigos de algunos subconjuntos dominantes se incluyen en un apéndice.
Citas
Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Machines. A Stochastic Approach to Combinatorial Optimization and Neural Computing . John Wiley & Sons, Chichester.
Biggs, N. (1974) Algebraic Graph Theory. Cambridge University Press.
Blokhuis, A.; Lam, C.W.H. (1984) “More coverings by rook domains”, Journal of Combinatorial Theory, Series A 36: 240–244.
Cameron, P.J.; van Lint, J.H. (1991) Designs, Graphs, Codes and their Links. London Mathematical Society Student Texts, 22, Cambridge University Press.
Davies, R.; Royle, G.F. (1997) “Graph domination, tabu search and the football pool problem”, Discrete Applied Mathematics 74(3): 217–228.
Garey, M.; Johnson, D. (1979) Computers and Intractability: a Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco.
Hämäläinen, H.O.; Rankinen, S. (1991) “Upper bounds for football pool problem and mixed covering codes”, Journal of Combinatorial Theory, Series A, 56: 84–95.
Knuth, D.E. (1981) Seminumerical Algorithms. Second edition, volume 2 of the book The Art of Computer Programming . Addison-Wesley, Reading, Mass.
Koschnick, K.U. (1993) “A new upper bound for the football pool problem for nine matches”, Journal of Combinatorial Theory, Series A, 62: 162–167.
van Laarhoven, P.J.M. (1988) “Theoretical and computational aspects of simulated annealing”, Centrum voor Wiskunde in Informatica, Tract 57.
van Laarhoven, P.J.M.; Aarts, E.J.L.; van Lint, J.H.; Wille, L.T. (1989) “New upper bounds for the football pool problem for 6, 7 and 8 matches”, Journal of Combinatorial Theory, Series A, 52: 304–312.
Österg̊ard, P.R.J.; Hämäläinen, H.O. (s.f.) “A new table of binary/ternary mixed covering codes”, Preprint.
Österg̊ard, P.R.J. (1994) “New upper bound for the football pool problem for 11 and 12 matches”, Journal of Combinatorial Theory, Series A, 67: 161–168.
Österg̊ard, P.R.J. (1995) “A combinatorial proof for the football pool problem for six matches”, Journal of Combinatorial Theory, Series A: 160–163.
Piza, E.; Trejos, J.; Murillo, A. (1998) “Global stochastic optimization techniques applied to partitioning”, in A. Rizzi et al. (Eds.) Advances in Data Science and Classification, Springer Verlag, Berlin: 185–191.
Wille, L.T. (1987) “The football pool problem for 6 matches: A new upper bound obtained by simulated annealing”, Journal of Combinatorial Theory, Series A, 45: 171–177.