Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
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 subconj...
| Autor principal: | |
|---|---|
| Formato: | Online |
| Idioma: | spa |
| Publicado: |
Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
2004
|
| Acceso en línea: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/243 |
| Sumario: | 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. |
|---|