Biblioteca CICESE

Edificio Dr. Nicolás Grijalva y Ortiz

Catálogo de tesis
Análisis de la factibilidad del diseño de algoritmos auto-estabilizantes para el conjunto independiente fuerte con peso máximo en uniciclos
Clasificación
31100
Resumen
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.
Nota de la tesis
Tesis para obtener el grado de Maestro en Ciencias en Ciencias de la Computación
Institución
Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California
Año de publicación
2018
Detalles físicos
ix, 87 hojas : ilustraciones
Temas
Computación
Algoritmos
2-packing
Computer science
Algorithms
Nota
Miembros del Comité: Fernández Zepeda José Alberto; Trejo Sánchez Joel Antonio; Brizuela Rodríguez Carlos Alberto; Chávez Pérez Ricardo Arturo
Incluye apéndice y referencias bibliográficas
Disponibilidad
Número de inventario Volumen Biblioteca Ubicación Estado Nota
31100 -- CICESE Colección de tesis Disponible
Cómo citar
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. ix, 87 hojas.
Opciones
Version en PDF de la tesis
Descargar texto completo... (949.88 KB)
 
 

CICESE

Carretera Ensenada-Tijuana No. 3918,
Zona Playitas, C.P. 22860,
Ensenada, B. C. México.

Teléfono: 01 (646) 175-05-00 ext 23044