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...
Guardado en:
Autor principal: | |
---|---|
Otros Autores: | |
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 |