Algoritmos que generan certificados ralos de k-conexidad en tiempo lineal

Ponente(s): Víctor Sánchez Flores

Dada una gráfica G=(V,E), un certificado de k-conexidad es un subconjunto E' de las aristas tal que la subgráfica G'=(V,E') es también k-conexa. Notemos que el caso k=1 corresponde con los Árboles generadores de peso mínimo. Sin embargo, para k>1 este problema es NP-completo por lo que los algoritmos que presentamos para conexidades mayores a 1, generan certificados ralos. Un certificado de k-conexidad es ralo si tiene O(k|V|) aristas. En este trabajo se exponen 3 algoritmos, cada uno con un enfoque distinto: secuencial, paralelo y distribuido. Cada uno de ellos genera certificados ralos en tiempo lineal. Además de la exposición individual de los algoritmos, haremos un análisis y comparación de los mismos tanto en su ejecución, su salida así como en su complejidad de tiempo.