Local dynamics for the calculation of global properties in graphs

Abstract

El problema de clasificación de densidad en grafos consiste en encontrar una dinámica local tal que, dado un grafo y una configuración inicial de 0's y 1's asignada a los nodos del grafo, la dinámica converja a la configuración de punto fijo 1's si la fracción de 1 es mayor que una densidad crítica (típicamente 1/2) y, de lo contrario, converja a la configuración de punto fijo 0's. Para resolver este problema seguimos la idea propuesta en un trabajo antrerior, donde los autores diseñaron un autómata celular inspirado en dos mecanismos: difusión y amplificación. Aplicamos este enfoque a diferentes clases de grafos bien conocidos: grafos completos, regulares, de estrella, Erdős-Rényi y Barabási-Albert. Un conjunto independiente maximal (MIS) es un conjunto maximal por inclusión de vértices no adyacentes por pares. El cálculo de un MIS es uno de los problemas centrales de la computación distribuida. En esta tesis presentamos y analizamos un algoritmo aleatorio distribuido de estado finito para calcular un MIS en grafos arbitrarios no dirigidos. Nuestro algoritmo es autoestabilizante, es decir, alcanza una salida correcta en cualquier configuración inicial. Analizamos el tiempo de convergencia del algoritmo propuesto, mostrando que en muchos casos el algoritmo converge en tiempo logarítmico con alta probabilidad.