Variaciones del Problema de Dominación y Separación en grafos

En esta tesis nos enfocamos en el estudio de cuatro variaciones del Problema de Dominación y Separación en grafos: los problemas de código de identificación, localización y dominación total en grafos. Estos problemas han sido desarrollados y estudiados activamente durante las ´ultimas décadas. Entre los desafíos relacionados con ellos nos proponemos determinar y/o aproximar el cardinal del mínimo código de identificación, conjunto de localización-dominación, conjunto de localización-dominación abierta o conjunto de localización-dominación total para diferentes clases de grafos. Es sabido que responder estas preguntas es de interés tanto teórico como práctico. La relevancia de estos problemas se debe a que modelan situaciones reales provenientes de variadas disciplinas, como por ejemplo el análisis de dispersión de enfermedades, detección de fallas en redes de comunicación y ubicación de alarmas de incendio o detectores de movimiento en establecimientos, edificios, viviendas, instalaciones,etc. Esta importancia práctica hace necesario el desarrollo de algoritmos exactos capaces de resolver instancias provenientes de aplicaciones del mundo real en tiempos computacionales razonables. Una manera a menudo exitosa de resolver esta clase de problemas, es a través de modelos de programación lineal entera sobre los cuales se realiza un estudio poliedral del espacio de soluciones. También aplicamos este abordaje para encontrar valores exactos del mínimo conjunto en cuestión, o estimaciones de estos parámetros para varias clases de grafos. Por otra parte, utilizamos la teoría de grafos para la obtención de los parámetros mencionados en ciertas familias de grafos. Finalmente, presentamos algoritmos que en tiempo lineal, resuelven los problemas de determinar la cardinalidad del mínimo código de identificación, conjunto de localización-dominación, conjunto de localización-dominación abierta y conjunto de localización-dominación total en los llamados grafos block.