Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/424| Diseño de algoritmos auto-estabilizantes para el problema del conjunto independiente fuerte S/C | |
| Joel Antonio Trejo Sánchez | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Computación,Conjunto independiente fuerte,Algoritmos distribuidos,Algoritmos autoestabilizantes | |
| Esta tesis se enfoca en el estudio del problema del conjunto independiente fuerte enalgoritmos distribuidos y en algoritmos auto-estabilizantes. Se presenta un algoritmoauto-estabilizante para elección de líder para un grafo arbitrario. Este algoritmo es óptimo dado que encuentra un líder en O(diam) rondas, donde diam es el diámetro delgrafo de entrada. Dicho algoritmo es un componente fundamental de los algoritmos dela tesis.En segundo lugar, se presenta un algoritmo auto-estabilizante que calcula un conjuntoindependiente fuerte máximo en un anillo. Posteriormente, se extiende dichoalgoritmo para calcular un conjunto independiente fuerte maximal en un cactus. Ambosalgoritmos mejoran la complejidad temporal de los resultados previos cuando elgrafo de entrada es un anillo o un cactus. Finalmente, se presenta un algoritmo distribuidoque calcula un conjunto independiente fuerte maximal en un grafo outerplanargeométrico. La complejidad temporal de este algoritmo es O(n) rondas, donde n es elnúmero de vértices en el grafo. Este algoritmo también calcula un conjunto independientefuerte máximo cuando el grafo de entrada es un anillo. La dificultad principal endiseñar estos algoritmos es que los procesadores sólo tienen una vista local del sistemay necesitan leer información a una distancia dos. Todos los algoritmos que se presentanen la presente tesis son determinísticos. This thesis focuses on studying the 2-packing set problem in distributed and selfstabilizingalgorithms. It presents a simple leader election self-stabilizing algorithm fora graph with arbitrary topology. This algorithm is optimal since it finds a leader inO(diam) rounds, where diam is the diameter of the input graph. This algorithm is afundamental component of the algorithms in the thesis.Second, we present a self-stabilizing algorithm that computes a maximum 2-packingset in a ring. Next, we extend such an algorithm to also compute a maximal 2-packingset in a cactus graph. Both algorithms outperform the time complexity of previousresults when the input graph is a ring or a cactus. Finally, we present a distributedalgorithm that computes a maximal 2-packing set in a geometric outerplanar graph.The time complexity of this algorithm is O(n) rounds, where n is the number of verticesin the graph. This algorithm also computes a maximum 2-packing set when the inputgraph is a ring. The main difficulty in designing these algorithms is that processorsonly have a local view of the system and they need to read information at distance-two.All the algorithms presented in this thesis are deterministic. | |
| CICESE | |
| 2014 | |
| Tesis de doctorado | |
| Español | |
| Trejo Sánchez,J.A.2014.Diseño de algoritmos auto-estabilizantes para el problema del conjunto independiente fuerte.Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.ix, 103 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 234671.pdf | Versión completa de la tesis | 1.69 MB | Adobe PDF | Visualizar/Abrir |