Aumentando óptimamente la nodo-conectividad de un ciclo en uno.

Abstract: “Definimos el problema de “aumentación de conectividad de grafos” de la forma siguiente: La entrada es un grafo G y un conjunto de aristas E, tal que G es k-conexo y G+E es (k+1)-conexo. Y la salida debe ser un subconjunto F de E de tamaño mínimo tal que G+F sea (k+1)-conexo.

Este tipo de problemas se enmarcan en el diseño de redes, muy importante en áreas tales como telecomunicaciones y electricidad. Muchos de estos problemas son NP-dificiles, por lo que es necesario diseñar algoritmos de aproximación para atacar el problema.

En este seminario mostraré un resumen de los resultados más importantes de los últimos años para el problema. Además, presentaré un resultado parcial en el caso que G es un ciclo. En este caso particular, se mejora el mejor valor conocido para el orden de aproximación, que era 2, a aproximadamente 1.92. Esto se puede ver como una generalización de los resultados de Gálvez et al., quienes trabajaron con la noción de ciclos y arista-conexidad.

Date: Jan 07, 2021 at 10:15:00 h
Venue: Modalidad Vía Online.
Speaker: Francisco Sanhueza Matamala
Affiliation: Universidad de Chile
Coordinator: Matías Pavez
More info at:
Event website
Abstract:
PDF

Posted on Jan 6, 2021 in Seminario de Grafos, Seminars