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

Guardado en:
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:
id I15-R121-2133-21858
record_format dspace
institution Universidad Nacional de Rosario
institution_str I-15
repository_str R-121
collection Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR)
language Español
orig_language_str_mv spa
topic Conjunto de identificación
Conjunto de localización- dominación
Conjunto de localización- dominación abierta
Conjunto de localización- dominación total
spellingShingle Conjunto de identificación
Conjunto de localización- dominación
Conjunto de localización- dominación abierta
Conjunto de localización- dominación total
Lucarini, Yanina P.
Variaciones del Problema de Dominación y Separación en grafos
topic_facet Conjunto de identificación
Conjunto de localización- dominación
Conjunto de localización- dominación abierta
Conjunto de localización- dominación total
description 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.
author2 Bianchi, Silvia M.
author_facet Bianchi, Silvia M.
Lucarini, Yanina P.
format doctoralThesis
Tésis de Doctorado
acceptedVersion
author Lucarini, Yanina P.
author_sort Lucarini, Yanina P.
title Variaciones del Problema de Dominación y Separación en grafos
title_short Variaciones del Problema de Dominación y Separación en grafos
title_full Variaciones del Problema de Dominación y Separación en grafos
title_fullStr Variaciones del Problema de Dominación y Separación en grafos
title_full_unstemmed Variaciones del Problema de Dominación y Separación en grafos
title_sort variaciones del problema de dominación y separación en grafos
publishDate 2021
url http://hdl.handle.net/2133/21858
http://hdl.handle.net/2133/21858
work_keys_str_mv AT lucariniyaninap variacionesdelproblemadedominacionyseparacionengrafos
bdutipo_str Repositorios
_version_ 1764820411454849026