[Todos CMAT] Seminario de Probabilidad y Estadística

[seminarios en cmat.edu.uy]

Seminario de Probabilidad y Estadística
----------------------------------------

Título: "Algoritmos "degree-greedy" para la exploración de grafos aleatorios y aplicaciones"

Expositor: Paola Bermolen (Fing.)

Resumen:
 
Trabajo conjunto con Matthieu Jonckheere (UBA), Federico La Rocca (IIE/FING) y
Manuel Saenz (UBA).    Los algoritmos de exploración de grafos nos permiten
entre otras cosas hallar conjuntos independientes, esto es, subconjuntos de
vértices tales que para cada par de vértices no hay aristas que los conecten.
Una característica interesante de un grafo es el tamaño del mayor conjunto
independiente, que se conoce como "independence number".  Sin embargo, su
cálculo es un problema NP-hard y tanto su caracterización como el diseño de
algoritmos para su cálculo son todavía problemas abiertos.  En esta charla vamos
a repasar algunos resultados previos sobre la caracterización de conjuntos
independientes para diferentes clases de grafos y los algoritmos existentes para
hallarlos.  A su vez, presentaremos dos nuevos algoritmos de exploración
secuencial de un grafo aleatorio para los cuáles caracterizamos su
comportamiento asintótico. Esto nos permite calcular el tamaño del conjunto
independiente descubiertos por dichos procesos de exploración.  Mostraremos que
estos algoritmos son un método eficiente a la hora de calcular o acotar el
independence number. Finalmente, estos resultados son aplicados para la
estimación de la capacidad de un red inalámbrica.
--------------------------------------------------------------------------------
Viernes 4/10 a las 10:30, Salón de seminarios del piso 14, CMAT

Contacto: Alejandro Cholaquidis - acholaquidis en hotmail.com
--------------------------------------------------------------------------------

Más seminarios en: http://www.cmat.edu.uy/seminarios
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.cmat.edu.uy/pipermail/todos/attachments/20191002/5874c9ad/attachment.html>