logo móvil
Contáctanos

¿cuántos leones se necesitan para despejar una cuadrícula?

Autores: Berger, Florian; Gilbers, Alexander; Grüne, Ansgar; Klein, Rolf

Idioma: Inglés

Editor: MDPI

Año: 2009

Descargar PDF

Acceso abierto

Artículo científico
2009

¿cuántos leones se necesitan para despejar una cuadrícula?


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Cuadrícula
Leones
Contaminación
Vértices
Dimensión
Problema

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
Consideramos un problema de persecución-evasión en el que algunos tienen la tarea de limpiar un grafo de rejilla cuyos nodos están inicialmente contaminados. La contaminación se propaga un paso por unidad de tiempo en cada dirección no bloqueada por un león. Un vértice se limpia de su contaminación cada vez que un león se mueve hacia él. Brass mostró que los leones no son suficientes para limpiar la -rejilla. En este artículo, consideramos el mismo problema en dimensión y demostramos que los leones son necesarios y suficientes para limpiar la -rejilla. Además, analizamos una variante del problema en la que los leones también pueden saltar de vértices de rejilla a vértices de rejilla no adyacentes.

Otros recursos que podrían interesarte

Temas Virtualpro