Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2537| Análisis de la factibilidad del diseño de algoritmos auto-estabilizantes para el conjunto independiente fuerte con peso máximo en uniciclos Feasibility analysis of the design of self-stabilizing algorithms for the maximum weighted independent set problem in unicycles | |
| DAVID ZHOU TAN | |
| José Alberto Fernández Zepeda Joel Antonio Trejo Sánchez | |
| Acceso Abierto | |
| Atribución | |
| Auto-estabilización, 2-packing, cactus, uniciclo Self-stabilization, 2-packing, cactus, unicycle | |
| En este trabajo se estudia el problema de encontrar el conjunto independiente fuerte (2-packing) con peso máximo, que suele aparecer en problemas de exclusión mutua, calendarización, etiquetado de mapas, entre otros. Este problema en grafos generales es NP-difícil, pero para grafos restringidos como el árbol, el uniciclo y el cactus, se han encontrado soluciones eficientes. En esta investigación se trabaja en los casos del cactus y del uniciclo. Para el cactus se propone un algoritmo secuencial basado en un algoritmo reciente en la literatura que resuelve el mismo problema pero en cactus sin peso, y se implementa en un lenguaje de programación orientado a objetos (Java). Para el uniciclo se diseña un algoritmo auto-estabilizante basado en la implementación anterior. Además se plantean los pasos para generalizar este ´ultimo para que funcione en un cactus. Los algoritmos auto-estabilizantes se utilizan en sistemas distribuidos donde se necesita asegurar estabilidad sin necesidad de que haya interacción humana, incluso cuando ocurren fallos transitorios, tales como cortes de energía y pérdidas de memoria. In this thesis we study the problem of finding the strong independent set (2-packing) with maximum weight, usually appearing in problems of mutual exclusion, tasks scheduling, map labeling, among others. The 2-packing problem in general graphs is NP-hard, but in restricted graphs such as trees, unicycles and cacti, efficient solutions have been found. In this research we work on cacti and unicycles. For the cacti, we propose a sequential algorithm based on a recent algorithm in the literature that solves the same problem in unweighted cacti. This new algorithm is implemented in a object oriented programming languaje (Java). For the unicycles we design a self-stabilizing algorithm based on the previous implementation. Also, we present the steps to generalize it for the cacti. Self-stabilizing algorithms are used in distribuited systems where it is necessary to ensure stability without human interaction, even when transient faults occur, such as energy cuts and memory leaks. | |
| CICESE | |
| 2018 | |
| Tesis de maestría | |
| Español | |
| Zhou Tan, D. 2018. Análisis de la factibilidad del diseño de algoritmos auto-estabilizantes para el conjunto independiente fuerte con peso máximo en uniciclos. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 87 pp. | |
| INGENIERÍA Y TECNOLOGÍA | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| Tesis David Zhou Tan_05_nov_2018.pdf | Versión completa de la tesis | 949.88 kB | Adobe PDF | Visualizar/Abrir |