Diseño de algoritmos distribuidos para el conjunto independiente fuerte.

Ponente(s): Joel Antonio Trejo Sánchez

Dado un grafo G=(V,E) un subconjunto S de V es un conjunto independiente fuerte (CIF) (2-packing en inglés) si dados dos elementos u,v de S, existen al menos tres aristas entre u y v. Se dice que un CIF S es maximal, si no existe un CIF S’, tal que S es subconjunto de S’. En particular, al CIF maximal de cardinalidad máxima, se le conoce como CIF máximo. Hochbaum y Shmoys [1] demostraron que encontrar un CIF de cardinalidad máxima pertenece a la clase de problemas NP-difícil. En contraparte, diseñar algoritmos voraces para encontrar un CIF maximal es trivial en el contexto secuencial. Sin embargo, en el contexto de los algoritmos distribuidos, se requieren estrategias mucho más sofisticadas para encontrar un CIF maximal, ya que cada vértice del grafo solo puede ver información de sus vecinos inmediados. En esta charla, se explica la estrategia que se utiliza para diseñar algoritmos distribuidos para dos topologías de grafos con ciertas restricciones. Primero se describe un algoritmo distribuido auto-estabilizante para encontrar un CIF maximal en un grafo cactus. Posteriormente, se describe un algoritmo distribuido para encontrar un CIF maximal en un grafo outerplanar geométrico. Además se presentan algunos retos para mejorar la complejidad temporal de estos algoritmos. [1] Hochbaum, D. S., & Shmoys, D. B. (1985). A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2), 180-184.