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.

Finalizó la especialización en Ciencias de la Computación para docentes primarios

El pasado 3 de julio se realizó el cierre del dictado de la primera cohorte de la "Especialización Docente de Nivel Superior en Didáctica de las Ciencias de la Computación: Aprendizaje y Enseñanza del Pensamiento Computacional y la Programación en el Nivel Primario".

Leer más: Finalizó la especialización en Ciencias de la Computación para docentes primarios

La Escuela de Posgrado comenzará a dictar dos nuevas carreras

La Escuela de Posgrado y Educación Continua (EPEC) de la FCEIA dará inicio, en agosto, al cursado de dos nuevas carreras de especialización: en Infraestructura de Datos Espaciales (IDEs) y en Ingeniería de Petróleo y Gas (PyG).

Leer más: La Escuela de Posgrado comenzará a dictar dos nuevas carreras

Día de la Cartografía, ¿por qué es importante esta ciencia para el desarrollo de las regiones?

El 26 de junio se celebra en Argentina el Día de la Cartografía en homenaje a la fecha de creación del Departamento Topográfico impulsado por Bernardino Rivadavia en 1826. La cartografía es la ciencia que se encarga del estudio y elaboración de la representación gráfica del territorio.

Leer más: Día de la Cartografía, ¿por qué es importante esta ciencia para el desarrollo de las regiones?

Graduado de la FCEIA y becario del IFIR ganó una beca internacional

Martín Toderi, egresado de la Licenciatura en Física y becario del Instituto de Física de Rosario, se convirtió recientemente en el único argentino en obtener una beca internacional que le permitirá continuar con sus investigaciones en el campo de las ópticas innovadoras para el estudio de componentes de la sangre. 

Leer más: Graduado de la FCEIA y becario del IFIR ganó una beca internacional

Tutorías desarrolló la charla “Ingeniería, ambiente y sustentabilidad”

El pasado 5 de junio el Área de Tutorías realizó la actividad “Ingeniería, ambiente y sustentabilidad” en el marco del Día Mundial del Medio Ambiente.

Leer más: Tutorías desarrolló la charla “Ingeniería, ambiente y sustentabilidad”

6 de junio: Día de la Ingeniería

La fecha conmemora la graduación del primer Ingeniero Civil de Argentina, Luis Augusto Huergo.

Leer más: 6 de junio: Día de la Ingeniería

¿Cómo afecta la redefinición del kilogramo y otras unidades de medida?

La Conferencia General de Pesas y Medidas (CGPM) aprobó en noviembre de 2018 la mayor revisión del Sistema Internacional de Unidades (SI) desde su creación en 1960. Se redefinieron cuatro unidades de base: el kilogramo, el ampere, el kelvin y el mol y se reformuló el metro, el segundo y la candela. 

Leer más: ¿Cómo afecta la redefinición del kilogramo y otras unidades de medida?

El Consejo Consultivo de Decanos de Santa Fe se reunió en la FCEIA

Se realizó una nueva reunión del Consejo Consultivo de Decanos de Facultades de Ingeniería de la Provincia de Santa Fe. En esta oportunidad, la sede del encuentro fue la FCEIA.

Leer más: El Consejo Consultivo de Decanos de Santa Fe se reunió en la FCEIA

Asumieron las nuevas autoridades de la FCEIA

El martes 21 de abril se realizó el acto de asunción de las nuevas autoridades para el periodo 2019-2023. La nueva Decana, Dra. Ing. Graciela Utges, y el Vicedecano, Ing. Damián Portaro, fueron elegidos en una sesión especial de Consejo Directivo en abril pasado. 

Leer más: Asumieron las nuevas autoridades de la FCEIA