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