El problema de la conexidad en el modelo computacional number-in-hand

Abstract

La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz de trabajar con cantidades masivas de datos, como son, por ejemplo, las redes sociales. En particular, se estudia la complejidad del problema CONEXIDAD de un grafo $G=(V,E)$ en el modelo computacional number-in-hand. Este problema consiste en decidir si un grafo $G$ es o no conexo. Por otro lado, a grandes rasgos, la complejidad que se considera aquí mide el largo de los mensajes (en bits) que los nodos deben comunicar para decidir CONEXIDAD. En primer lugar, se demuestra que la complejidad, en el caso en que el grafo $G$ es arbitrario, es al menos $f(n)$, donde $f(n) = \log n - (\log \log n +1+ \log n /n)$. Sin embargo, esta fórmula no aporta información alguna cuando el grafo $G$ posee $n<27$ nodos, pues $f(n) \leq 1$ para tales valores. Es decir, indica que la cantidad de bits que se tienen que comunicar es al menos $\leq 1$, lo que es evidente. Por esta razón, se profundiza el estudio analizando grafos pequeños, y se demuestra que 1 bit no es suficiente para decidir el problema en tal caso. Por otro lado, la cota expuesta se obtiene a partir de una reducción que construye un grafo de grado no acotado. Por lo tanto, $f(n)$ puede ser poco ajustada para la familia de grafos de grado acotado. Así pues, se complementa el trabajo restringiéndose a esta clase de grafos, con el fin de saber si en tal caso existe una mejor cota para la complejidad de CONEXIDAD en el modelo number-in-hand. Usando técnicas de complejidad comunicacional se encuentra una cota inferior de $\Omega(\log n)$. Más aún, se demuestra que esta cota es ajustada para esta clase de grafos.