Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/442| Algoritmo para encontrar el conjunto independiente fuerte máximo sobre un grafo tipo cactus Algorithm to find the maximum 2-Packing set in a cactus graph | |
| Alejandro Flores Lamas | |
| Jose Alberto Fernández Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Ciencias computacionales | |
| Esta tesis analiza el problema del conjunto independiente fuerte (CIF) máximo sobre un grafo cactus K = (VK,EK). El CIF es un problema bien conocido en el área de teoría de grafos y algoritmos, que se de?ne como subconjunto de vértices del grafo tal que para todo par u,v ? CIF, la trayectoria más corta entre ellos es de al menos tres aristas. La solución a esta problemática tiene diversas aplicaciones entre las que se incluyen el estudio de moléculas y átomos, modelado de redes, plani?cación de rutas, de operaciones y asignación de instalaciones. En el área de teoría de juegos, existen aplicaciones en el campo económico, ingenieril e incluso bélico. Hasta el momento, se desconoce la existencia de algún algoritmo para el grafo cactus o para el grafo general capaz de resolver el CIF m´aximo en tiempo polinomial y las propuestas que existen únicamente encuentran conjuntos máximos en topologías muy restringidas o conjuntos maximales en grafos más complejos. En este trabajo, se resuelve el CIF máximo sobre grafos tipo cactus mediante un algoritmo (CIF-MAXIMUM-CACTUS) que descompone el grafo en componentes biconectados y que mediante un recorrido sobre el grafo e información acerca de los componentes visitadosy vértices previamentemarcados, encuentra el CIF en cada componente biconectado. La unión de los vértices marcados produce un CIF máximo sobre el grafo original. La complejidad computacional del CIF-MAXIMUM-CACTUS es de O(n2) unidades de tiempo, donde |VK| = n. El algoritmo se codi?cación en lenguaje JAVA versión 1.8.0 05 y se alimentó con dos conjuntos de prueba: el primero con grafos simples cuyo CIF máximo es conocido fácilmente identi?cable; el segundo con 120 grafos (árboles, cadenas de ciclos, sistemas de engranes y cactus) generados de forma aleatoria. El análisis formal del algoritmo, así como los resultados obtenidos mediante la implementación y evaluación de los casos de prueba, demuestran la corrección del algoritmo propuesto. In this thesis we analyze the problem of the maximum 2-packing set in a cactus graph K = (VK,EK). The 2-packing set is a well known problem in the ?elds of graph theory and algorithms. In a graph G = (V,E), a subset S ? V is a 2-packing if for every pair u,v ? S the shortest path between them is at least three edges long. The solution to this problem results in a wide range of applications such as the study of molecules and atoms, network modeling, route planning and operations, and allocation offacilities. Also, there are several applications in game theory, ranging from economics, engineering and warfare. Hitherto, to the best of the author knowledge, there is no algorithm for the cactus nor do exists for the general graph to solve the maximum 2-packing set in polynomial time; other proposals ?nd maximum sets in restricted graph topologies or maximal sets in more complex graphs. In this study, we propose an approach to solve the maximum 2-packing set pro- blem in cactus graphs using an algorithm (CIF-MAXIMUM-CACTUS) which decomposes the graph in biconnected components and ?nds its 2-packing set following a path through the graph and applying previously gathered information about visited components and marked vertices. The union of marked vertices produces a maximum 2-packing set in the original graph. The running time of the algorithm is O(n2) time units, where|VK| = n. The CIF-MAXIMUM-CACTUS was implemented in JAVA 1.8.0 05 and two test sets were em- ployed to evaluate its performance: the former includes simple graphs which its maximum 2-packing set is known or easily identi?ed; the other consists of 120 randomly generated graphs (trees, cycle chains, cycle arrangements and cactus). The formal proof of the al- gorithm, its implementation and results in the test sets show the algorithm’s correctness. | |
| CICESE | |
| 2014 | |
| Tesis de maestría | |
| Español | |
| Flores Lamas,A.2014.Algoritmo para encontrar el conjunto independiente fuerte máximo sobre un grafo tipo cactus.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xi, 87 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 236611.pdf | Versión completa de la tesis | 31.43 MB | Adobe PDF | Visualizar/Abrir |