El problema de la conexidad en el modelo computacional number-in-hand
| Autor: | Lizama Orellana, Antonio Andrés |
|---|---|
| Jazyk: | španělština |
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Tesis |
| Popis: | Ingeniero Civil Matemático 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 |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|