Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3632| Algoritmos para el problema del conjunto independiente fuerte en grafos dispersos Algorithms for solving the 2-packing problem in sparse graphs | |
| Carlos Alberto Oliva Moreno | |
| José Alberto Fernández Zepeda Joel Antonio Trejo Sánchez | |
| Acceso Abierto | |
| Atribución | |
| algoritmos para grafos,conjunto independiente fuerte,2-packing, cactus lineal,heurística,simulación algorítmica Graph algorithms,strong independent set,2-packing,lineal cactus, heuristic,algorithm simulation | |
| Sea G = (VG, EG) un grafo conectado y no dirigido, un conjunto independiente fuerte (abreviado por las siglas CIF) es un conjunto S ⊆ VG tal que, para cualquier par de vértices en S, la distancia entre ellos es de al menos tres aristas. El problema de encontrar el CIF de la mayor cardinalidad posible en un grafo arbitrario es un problema NP-difícil. En este trabajo de tesis, se propusieron dos algoritmos para resolver este problema. El primero consiste de una heurística voraz que se puede aplicar sobre grafos arbitrarios pero que solo está garantizado que puede encontrar un CIF maximal. El segundo es un algoritmo secuencial que puede encontrar el CIF máximo en un grafo cactus restringido, denominado cactus lineal, en O(n) pasos. También se hizo una comparación experimental entre la heurística voraz y el Gurobi, un solucionador contemporáneo de programación entera mixta. Esta comparación demostró que la heurística requiere menos tiempo de ejecución que el Gurobi en todos los casos probados, a cambio de una reducción promedio en la cardinalidad de la solución de no más del 10%. También se demostró que, cuando el grafo es grande, la heurística encuentra soluciones de igual o mayor cardinalidad a la del Gurobi en el caso de los modelos de grafos aleatorios de Gilbert y Watts-Strogatz y en grafos conectados aleatorios. Let G = (VG, EG) be an undirected and connected graph, a 2-packing set is the set of vertices S ⊆ VG such that, for any pair of vertices in S, the distance between them is at least three. Finding a 2-packing set of maximum possible cardinality in an arbitrary graph constitutes an NP-hard problem. In this work, we propose two algorithms for tackling this problem. The first one consists of a greedy heuristic that can be applied on arbitrary graphs, but which is only guaranteed to find a maximal 2-packing set. The second one consists of a sequential algorithm that can find the maximum 2-packing set in a restricted kind of cactus graph, called linear cactus, in O(n) time. An experimental comparison was also performed between the greedy heuristic and Gurobi, a contemporary mixed-integer programming solver. This showed that the heuristic requires less running time than Gurobi in all test cases, in exchage of an average reduction in the cardinality of the solution that is no larger than 10%. It was also shown that, for large graphs, the heuristic finds solutions of equal or greater cardinality than Gurobi in the case of graphs from the Gilbert and Watts-Strogatz random graph models as well as random connected graphs. | |
| CICESE | |
| 2021 | |
| Tesis de maestría | |
| Español | |
| Oliva Moreno, C.A. 2021. Algoritmos para el problema del conjunto independiente fuerte en grafos dispersos. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 90 pp. | |
| HEURÍSTICA | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_Carlos Alberto Oliva Moreno_09 nov 2021.pdf | Versión completa de la tesis | 640.44 kB | Adobe PDF | Visualizar/Abrir |