[Todos CMAT] Defensa Tesis de Maestría del Ing. Pablo Sartor: viernes 11/03, 10:00 hs.

[Franco Robledo]

Estimados investigadores y estudiantes:

Me complace informarles acerca de la Defensa Pública de la Tesis de 
Maestría en Informática-PEDECIBA del Ing. Pablo Sarto Del Giudice.

Día: viernes 11 de marzo de 2011.

Hora: 10:00.

Lugar: Salón de Seminarios (Instituto de Computación, Facultad de 
Ingeniería)

Título de la tesis: “Problema General de Steiner en Grafos: Resultados 
Teóricos y Algoritmos GRASP para la versión Arista-Disjunta".

Director de Tesis: Dr. Ing. Franco Robledo Amoza,
Co-Director de Tesis: Dr. Ing. Eduardo Canale.

El Tribunal estará integrado por:

• Dra. Alejandra Beghelli (Revisora): investigadora asociada de 
University College of London.
• MSc. Ing. Omar Viera: Director del Dpto. de Investigación Operativa, INCO.
• Dr. Ing. Álvaro Martín: docente INCO, investigador PEDECIBA.

Resumen:

El Problema Generalizado de Steiner en Grafos (GSP) es un problema 
NP-hard de cobertura minimal de grafos con requerimientos de redundancia 
de conectividad, muy adecuado para modelar problemas reales de diseño 
topológico de redes de comunicación. La resolución determinística del 
problema sólo es factible para instancias de tamaño muy limitado, siendo 
en general para casos reales necesario recurrir a técnicas heurísticas 
para la generación de soluciones de bajo costo con un consumo razonable 
de recursos de cómputo y tiempo de ejecución.
Los problemas se clasifican como de nodo-conectividad o 
arista-conectividad, según exijan o no los requerimientos de redundancia 
que no se compartan nodos intermedios entre caminos múltiples para 
conectar a las mismas parejas de nodos, modelándose así situaciones en 
las que tanto nodos como aristas pueden fallar, o solamente las aristas 
pueden hacerlo.

En este trabajo, haciendo uso de una técnica metaheurística conocida 
como GRASP (Greedy Randomized Adaptive Search Procedure), extendemos las 
ideas planteadas en un trabajo previo para la versión de 
nodo-conectividad del GSP, hacia la versión de arista-conectividad. Se 
estudia la relación entre ambas versiones del problema, así como las 
complejidades introducidas por el modelo de arista-conectividad y se 
proponen mejoras a los algoritmos existentes. Proponemos también un 
mecanismo alternativo de creación voraz de soluciones y un mecanismo 
recursivo general para la implementación de metaheurísticas que generen 
soluciones para el GSP, sobre lo cual esperamos basar futuros trabajos 
de investigación.


Saludos cordiales,
Dr. Ing. Franco Robledo Amoza