El problema del bombero con costos de defensa dinámicos

Área de la Ciencia:

• Teoría de grafos; Complejidad computacional; Teoría de juegos

Sus antecedentes:

• El problema clásico del bombero modela la propagación de contagios en grafos, con el objetivo de proteger vértices.; Es computacionalmente difícil pero resoluble en clases de grafos restringidas.

Objetivo del estudio:

• Introducir y analizar el Problema de la Función de Costo del Bombero, una variante con costos de defensa de vértigos dependientes del tiempo y del estado.; Investigar su complejidad computacional y tratabilidad en varias clases de grafos.

Principales métodos:

• Definir el Problema de la Función de Costo del Bombero y analizar su complejidad.; Utilizar lógica mónadica de segundo orden para probar la tratabilidad con parámetros fijos.; Realizar investigaciones empíricas comparando diferentes estrategias heurísticas.

Principales resultados:

• El problema de la Función de Costo es computacionalmente difícil, incluso en árboles donde el problema clásico es tratable.; Es tratable en grafos completos, grafos con longitud de camino acotada y ciertos árboles.; Se demostró la tratabilidad con parámetros fijos con respecto al ancho de árbol, presupuesto y paso de tiempo máximo.; Los resultados empíricos muestran que la efectividad heurística varía con la estructura del grafo; las estrategias basadas en el estado superan a las basadas en el grado.

Conclusiones:

• El Problema de la Función de Costo del Bombero presenta nuevos desafíos computacionales pero es manejable para parámetros y estructuras de grafos específicos.; La elección heurística es crítica y depende del grafo y las funciones de costo específicas involucradas en la modelización de contagios.