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

Descripción completa

Detalles Bibliográficos
Autor principal: Lucarini, Yanina P.
Otros Autores: Bianchi, Silvia M.
Formato: doctoralThesis Tésis de Doctorado acceptedVersion
Lenguaje:Español
Publicado: 2021
Materias:
Acceso en línea:http://hdl.handle.net/2133/21858
http://hdl.handle.net/2133/21858
Aporte de:Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario Ver origen
Descripción
Sumario: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.