El problema de dominación en grafos. Parte 2

Dra. Silvia Bianchi
sbianchi@fceia.unr.edu.ar

Los problemas de empaquetamiento y el cubrimiento de conjuntos son dos conceptos duales fundamentales en optimización combinatoria, los cuales son equivalentes a través de transformaciones apropiadas. Estos problemas son relevantes en la práctica, pero difíciles de resolver en general. Una manera a menudo exitosa de resolver esta clase de problemas es el enfoque poliedral relativo al espacio de soluciones del problema. En este proyecto en particular, abordamos aplicaciones del problema de cubrimiento de conjuntos que provienen del problema de dominación en grafos y sus variantes. En particular se estudiarán los siguientes temas: TEMA 1: Problema de dominación en grafos redes. Numerosas aplicaciones pueden ser modeladas como problemas de dominación en grafos (ver Henning (1997)). El problema de dominación clásico en un grafo es el problema de hallar un conjunto dominante de cardinal mínimo, es decir, un subconjunto de vértices de cardinal mínimo que tenga intersección no vacía con las vecindades cerradas del grafo. Este problema admite una formulación en términos del problema de cubrimiento de conjuntos. El enfoque poliedral ha sido de gran importancia para la resolución del problema y ha contribuido a la construcción y mejora de algoritmos específicos de resolución de algunas instancias. En particular, el problema de dominación en grafos redes se traduce en el problema de cubrimiento sobre matrices circulantes. TEMA 2: Problema de códigos de identificación en grafos. Habitualmente, las distintas aplicaciones que se modelan como problemas de dominación en grafos, imponen restricciones adicionales a los conjuntos dominantes, surgiendo de esta manera variaciones del problema (ver Henning (1997)). En efecto, a partir del concepto de dominación en grafos se modelan entre otros, problemas de locación de servicios (contenedores de residuos domiciliarios, hospitales, estaciones de bomberos, cajeros automáticos, etc.). Ejemplos clásicos son la detección de incendios en edificios y la detección de fallas en redes de procesadores. En estos casos se necesita instalar detectores de incendio o de fallas en ciertos lugares. Los detectores son suficientemente potentes como para detectar el problema incluso en los sitios contiguos a los lugares en donde se encuentran, por lo tanto se pretende instalar la menor cantidad de detectores posibles de manera que a partir del conjunto de detectores que dieron la alarma, se pueda identificar el sitio exacto en donde se ha producido la amenaza. Este conjunto de detectores es lo que se conoce como un código de identificación y el problema de cubrimiento de conjuntos también permite la formulación del problema de mínimo código de identificación como un programa entero.

SASE 2019: concurso para estudiantes

24-04-2019 Gacetillas

Del 17 al 19 de julio se desarrollará en la FCEIA el Simposio Argentino de Sistemas Embebidos 2019 (SASE). Entre sus objetivos el SASE busca fomentar la interacción industria-academia en...

Seguir Leyendo

6º Convocatoria de Proyectos de Vinculación Tecnológica y De…

16-04-2019 Gacetillas

La UNR lanza la 6º Convocatoria a Proyectos de Vinculación Tecnológica y Desarrollo Productivo “Vinculación Inclusiva” 2019. La misma permanecerá abierta hasta el 27 de mayo y se financiarán 20...

Seguir Leyendo
Más novedades

Diego Saikin visitó la FCEIA y contó su experiencia en el proyecto Bereshit

De Argentina a Israel y de Israel a la Luna. El argentino Diego Saikin visitó la FCEIA para contar su experiencia como integrante del equipo israelí SpaceIL, responsable de conceptualizar y crear a Bereshit”, la primera misión privada a la Luna en la historia.

Leer más: Diego Saikin visitó la FCEIA y contó su experiencia en el proyecto Bereshit

¿Cómo influye el cambio generacional en la educación?

Beatriz Salemme Correa Cortela es Doctora y Máster en Educación para la Ciencia y hace algunas semanas visitó la FCEIA para dictar el curso de Posgrado "Desafíos de la docencia en la Enseñanza Superior en el área de Ciencias Exactas y Naturales. Posibles abordajes y enfrentamientos". Durante su estadía en la ciudad compartió sus conocimientos sobre nuevas metodologías de enseñanza y la vinculación que existe entre escuela y universidad.

Leer más: ¿Cómo influye el cambio generacional en la educación?

La FCEIA eligió a sus nuevas autoridades

El lunes 22 de abril se realizó una sesión especial de Consejo Directivo donde los consejeros realizaron la votación para elegir a las próximas autoridades de la FCEIA, siendo electa como Decana la Ingeniería Electricista y Doctora en Educación, Graciela Utges.

Leer más: La FCEIA eligió a sus nuevas autoridades

La experiencia de un graduado en el Heidelberg Laureate Forum

Demian Goos es graduado de la Licenciatura en Matemática de la FCEIA y doctorando de nuestra Universidad. En 2017 participó durante una semana del Heidelberg Laureate Forum, un evento que reúne reconocidos matemáticos con jóvenes investigadores.

Leer más: La experiencia de un graduado en el Heidelberg Laureate Forum

Nodocente de la FCEIA viajó a España para capacitarse

A partir del Programa de Ayuda de Viaje al Extranjero (AVE), Silvia Saabedra, quien se desempeña en el Laboratorio de Informática de la Escuela de Ingeniería Electrónica, viajó a España para realizar tareas de intercambio y capacitación en el desarrollo, funcionamiento y mantenimiento de sistemas informáticos y  redes.

Leer más: Nodocente de la FCEIA viajó a España para capacitarse

Día del investigador científico

Cada 10 de abril se celebra en Argentina el día del Investigador Científico, en homenaje al nacimiento del Dr. Bernardo Houssay (1887-1971).

Leer más: Día del investigador científico

Las Cátedras de Introducción a la Ingeniería se reunirán en Rosario

El 1 de noviembre de 2019 la FCEIA será sede del V Encuentro Nacional de Cátedras de Introducción a la Ingeniería.

Leer más: Las Cátedras de Introducción a la Ingeniería se reunirán en Rosario

Información importante sobre las elecciones estudiantiles 2019

Del 9 al 11 de abril próximo se desarrollarán en la FCEIA las elecciones correspondientes al claustro estudiantil. Los alumnos de la Facultad que se encuentran en el padrón podrán elegir Centro de Estudiantes y sus representantes en el Consejo Directivo de la Facultad.

Leer más: Información importante sobre las elecciones estudiantiles 2019

Reunión Nacional de Educación en Física en la FCEIA

Del 30 de septiembre al 4 de octubre se desarrollará en Rosario la XXI Reunión Nacional de Educación en Física (REF) bajo el lema “El desafió de enseñar Física”.

Leer más: Reunión Nacional de Educación en Física en la FCEIA