Jorge Urrutia
13/05/2008
de 12:00 a 13:00
Dónde Salón "Graciela Salicrup"
Resumen:
En esta plática haremos un resumen de una nueva clase de algoritmos que resuelven problemas de tipo global en redes ad-hoc unitarias mediante algoritmos de tipo local. Un algoritmo local es un algoritmo en el que cada nodo sólo conoce información de nodos a distancia k contante de él mismo, con la condición adicional, que no permitimos que la información contenida en un nodo se disperse por la red. Esta última condición obedece a restricciones reales en redes como INTERNET que son muy dinámicas, y es difícil suponer que se conoce la topología de las mismas.
Por ejemplo, dada una red inalámbrica unitaria, queremos calcular una subgráfica plana de la misma, o calcular una aproximación a una subred cercana al árbol generador de peso mínimo. Presentaremos algunos algoritmos tales como coloración de aristas de una red, problemas de ruteo, etc., así como aplicaciones de estos algoritmos a redes celulares (redes que se comportan como las redes de teléfonos celulares).
La plática está basada en el artículo:
J. Urrutia, "Local solutions for global problems in wireless networks", Journal of Discrete Algorithms 5 (2007), 395-407.
Dicho artículo está disponible en mi página web:
http://www.matem.unam.mx/~urrutia/online_papers/index.html
Temas: