Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2542| Estudio de factibilidad para resolver el problema 2-packing máximo en tiempo polinomial en grafos outerplanares Feasibility study to solve the maximum 2-packing set problem in polynomial time in outerplanar graphs | |
| Alejandro Flores Lamas | |
| José Alberto Fernández Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos para grafos, conjunto 2-packing, grafo 1-outerplanar, desmembración de árbol, cactus. Graph algorithms, 2-packing set, 1-outerplanar graph, tree decomposition, cactus. | |
| Este trabajo de investigación se centra en el área de análisis y diseño de algoritmos para grafos, tanto centralizados como distribuidos. Sea G = (VG, EG) un grafo no dirigido, donde |VG| = n. Un subconjunto Ŝ ⊆ VG es un conjunto 2-packing si para cada par de vértices en Ŝ, la longitud del camino más corto entre ellos es de al menos tres aristas. Un conjunto 2-packing Ŝ es maximal si no existe otro conjunto 2-packing Ŝ’ tal que Ŝ ⊆ Ŝ’. Un conjunto 2-packing es máximo si es el conjunto de mayor cardinalidad entre todos los conjuntos 2-packing maximales. En este documento se discute el problema de encontrar un conjunto 2-packing en algunos grafos planos en tiempo polinomial. Un grafo plano es el que se puede dibujar en un plano de tal forma que las aristas sólo se intersectan en sus extremos. El cactus es un grafo plano donde cualquier arista pertenece a lo más a un ciclo. Un grafo 1-outerplanar es un grafo plano donde todos sus vértices yacen en el borde externo del mismo. Un grafo Halin es un grafo plano que se construye al conectar las hojas de un dibujo plano de un árbol (con al menos cuatro vértices, ninguno de ellos de grado dos) para que formen un ciclo. La primera contribución del presente trabajo de investigación consiste del diseño de un algoritmo de programación dinámica que encuentra un conjunto 2-packing máximo en un grafo cactus en O(n2) unidades de tiempo. La segunda contribución consiste del diseño de un algoritmo que encuentra un conjunto 2-packing máximo en un grafo 1-outerplanar en O(n) unidades de tiempo. Finalmente, la tercera contribución consiste del diseño de un algoritmo distribuido que encuentra un conjunto 2-packing maximal en un grafo Halin en O(n) unidades de tiempo. Se conjetura que las técnicas empleadas para el desarrollo de estos algoritmos podrían servir como base para desarrollar algoritmos similares para el problema del k-packing maximal y máximo en este tipo de grafos en tiempo polinomial. This research project focuses on the analysis and design of graph algorithms, both centralized and distributed. Let G = (VG, EG) be an undirected graph, where |VG| = n. A subset Ŝ ⊆ VG is a 2 -packing set if for every pair of vertices in Ŝ, the shortest path between them is at least three edges long. A 2-packing set Ŝ is maximal if it does not exist other 2-packing set Ŝ’ such that Ŝ ⊆ Ŝ’. A maximum 2-packing set is the one of largest cardinality among all maximal 2-packing sets. This document addresses the problem of finding a 2-packing set in some planar graphs in polynomial time. A planar graph has an embedding on a plane in such a way that its edges intersect only at their endpoints. The cactus is a planar graph such that any edge belongs to at most one cycle. A 1-outerplanar graph is a planar graph for which all its vertices lie on the boundary of the graph. A Halin graph is a planar graph constructed by connecting the leaves of a planar embedding of a tree (with at least four vertices, none of them of degree two) into a cycle. The first contribution of this work consists of the design of a dynamic programming algorithm that finds a maximum 2-packing set in a cactus graph in O(n2) time units. The second contribution consists of the design of an algorithm that finds a maximum 2-packing set on a 1-outerplanar graph in O(n) time units. Finally, the third contribution consists of the design of a distributed algorithm that finds a maximal 2-packing set on a Halin graph in O(n) time units. We conjecture that the techniques used for the design of these algorithms could serve as a basis to develop similar algorithms for the maximal and maximum k-packing set problem in these type of graphs in polynomial time. | |
| CICESE | |
| 2018 | |
| Tesis de doctorado | |
| Español | |
| Flores Lamas, A. 2018. Estudio de factibilidad para resolver el problema 2-packing máximo en tiempo polinomial en grafos outerplanares. Tesis de Doctorado en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 103 pp. | |
| LENGUAJES ALGORÍTMICOS | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_Flores_Lamas_Alejandro_12_nov_2018.pdf | Versión completa de la tesis | 4.43 MB | Adobe PDF | Visualizar/Abrir |