<div style="max-width:40em;text-align:justify;">                
                <h2 style="font-size:1.2em;">Seminario de Probabilidad y Estadística</h2>
                <h3 style="font-size:1em;">Título: <em>Algoritmos "degree-greedy" para la exploración de grafos aleatorios y aplicaciones</em></h3>
                <h3 style="font-size:1em;">Expositor: Paola Bermolen <span style="font-weight:400;">(Fing.)</span></h3>
                <div style="font-size:1em!important;"><p><b>Resumen: </b><br/><span>Trabajo conjunto con Matthieu Jonckheere (UBA), Federico La Rocca (IIE/FING) y Manuel Saenz (UBA).</span><br/><br/><span>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.</span></p></div>                
                <hr>
                <p style="font-size:1em;"><b>Viernes 4/10 a las 10:30</b><br>
                    <b>Salón de seminarios del piso 14, CMAT</b>
                </p>
                <p style="font-size:1em;"><b>Contacto: </b>Alejandro Cholaquidis - <a href="mailto:acholaquidis@hotmail.com">acholaquidis@hotmail.com</a></p>              
                <hr>  
                
                Más seminarios en: <a href="http://www.cmat.edu.uy/seminarios">http://www.cmat.edu.uy/seminarios</a>

            </div>