Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3557| Diseño de algoritmos auto-estabilizantes para grafos Halin Design of self-stabilizing algorithms for Halin graphs | |
| Tadeo Alán Gutiérrez Medina | |
| José Alberto Fernández Zepeda Joel Antonio Trejo Sánchez | |
| Acceso Abierto | |
| Atribución | |
| Auto-estabilización, Halin Self-stabilization, Halin | |
| Descomponer un grafo en componentes más simples es una tarea fundamental para el diseño de muchos algoritmos. En el caso de los grafos Halin, al estar construidos con un árbol y un ciclo, resulta de especial interés identificar estos componentes, dado que los mismos se han estudiado ampliamente. Existen algunos algoritmos que realizan una identificación de estos componentes en un número de pasos que es proporcional al número de vértices en el grafo; sin embargo, estos algoritmos son muy complejos. En este trabajo se propone una serie de algoritmos para realizar esta tarea. Estos algoritmos se ejecutan tan rápido como los anteriores, son mucho más sencillos, y además tienen la propiedad de ser auto-estabilizantes. Los algoritmos auto-estabilizantes son algoritmos ejecutados coordinadamente por varios procesadores en los que se asegura el correcto funcionamiento del sistema computacional, aún en la presencia de fallas transitorias. Una falla transitoria es el cambio del valor de alguna variable de un procesador, generalmente producido por ruido eléctrico. Estas fallas provocan errores lógicos en la ejecución del algoritmo, pero no alteran el funcionamiento de los procesadores. El algoritmo auto-estabilizante es capaz de detectar estos errores lógicos y corregirlos. Además, usando una lógica similar al primer algoritmo propuesto, se propone un segundo algoritmo que parte al conjunto de aristas del grafo en clases llamadas orejas. Las aristas de cada oreja tienen la propiedad de formar trayectorias simples en el grafo. Este tipo de algoritmos es fundamental para resolver algunos problemas más complejos, dado que facilitan el realizar una búsqueda exhaustiva sobre el grafo. Hasta donde el autor de este trabajo de investigación tiene conocimiento, estos son los primeros algoritmos auto-estabilizantes que resuelven estos problemas para los grafos Halin. Many algorithms benefit from decomposing a graph into simpler components. A Halin graph is the combination of a tree and a cycle. Both of these structures are heavily studied. For this reason, it is helpful to identify these components in Halin graphs. There are some algorithms in Halin graphs that identify the mentioned components in a time that is proportional to the number of vertices; nevertheless, these algorithms are complex. In this document, we propose an algorithm that solves this problem. Our algorithm is as fast as previous algorithms, but it is simpler and have the self-stabilization property. Self-stabilizing algorithms are algorithms that run on several processors and guarantee that the algorithms work properly, even in the presence of transient faults. A transient fault is a change in any variable’s value on any processor, generally produced by electric noise. These faults generate logical errors in the algorithm’s execution but do not alter the processors’ general behavior. A self-stabilizing algorithm is capable of detecting these logical errors and fixing them without external intervention. Using a similar approach, we also propose an algorithm that divides the graph’s edges into classes named ears. The edges of each ear have the property that they simple paths. This algorithm is fundamental to solve more complex problems, as it eases the searching process in a graph. As far as the author of this thesis knows, these are the first self-stabilizing algorithms that solve Halin graphs’ problems. | |
| CICESE | |
| 2021 | |
| Tesis de maestría | |
| Español | |
| Gutiérrez Medina, T.A. 2021. Diseño de algoritmos auto-estabilizantes para grafos Halin. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 71 pp. | |
| DISPOSITIVOS DE TRANSMISIÓN DE DATOS | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_Tadeo Alan Gutierrez Medina_26abril.pdf | Versión completa de la tesis | 1.89 MB | Adobe PDF | Visualizar/Abrir |