Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3559| Algoritmo de enumeración de cliques maximales en grafos k-outerplanares, usando descomposición de árbol Maximal clique enumeration algorithm in k-outerplanar graphs, using tree decomposition | |
| FRANCISCO GONZALEZ DOMINGUEZ | |
| José Alberto Fernández Zepeda Alejandro Flores Lamas | |
| Acceso Abierto | |
| Atribución | |
| Algoritmo para grafos, enumeración de cliques maximales, descomposición de árbol, anchura de árbol, grafo outerplanar, grafo k-outerplanar, problema del clique Graph algorithms, maximal clique enumeration, tree decomposition, treewidth, outerplanar graph, k-outerplanar graph, clique problem | |
| Un grafo G = (V, E) es una estructura discreta compuesta por el conjunto de vértices V y el de aristas E. Para un grafo G, un clique es un subgrafo para el cual cada par de vértices está conectado por una arista. Un clique maximal en G es aquel que no está contenido en otro clique más grande en G. El problema de enumeración de cliques consiste en enumerar todos los cliques maximales en G. Este problema pertenece a la clase N P-Difícil cuando G es arbitrario, y no se conocen algoritmos eficientes que lo resuelva. En el presente trabajo de investigación se propone el algoritmo DP-CLIQUE, el cual resuelve el problema anterior cuando el grafo de entrada es k-outerplanar. Un grafo k-outerplanar es un grafo plano, que al quitarle los vértices que tocan la región infinita del plano que rodea al grafo, así como sus aristas incidentes, se genera un grafo (k − 1)-outerplanar. El algoritmo DP-CLIQUE se auxilia de dos algoritmos del estado del arte. El primer algoritmo calcula la descomposición de árbol de un grafo kouterplanar. Una descomposición de árbol es una transformación del grafo de entrada a un árbol, en el cual, cada uno de sus nodos tiene atributos especiales. Posteriormente, se utiliza otro algoritmo que genera una descomposición de árbol agradable a partir de la descomposición anterior. La descomposición de árbol agradable tiene restricciones adicionales que facilitan su procesamiento. El tiempo de ejecución del algoritmo DP-CLIQUE es de O (τ + 1) · n · 2 τ+1 unidades de tiempo, donde n es el número de vértices en el grafo de entrada, y τ la anchura de árbol de G. La anchura de árbol de un grafo G es una medida que indica qué tan cercano es G a un árbol. Este tiempo de ejecución es polinomial en n, si τ es una constante. En particular, τ es una constante cuando k es una constante. Este tiempo de ejecución es equivalente al del mejor algoritmo del estado del arte, cuando k es constante, pero usa una técnica alternativa. Hasta donde el autor de este trabajo tiene conocimiento, el algoritmo DP-CLIQUE es el primero en resolver el problema mencionado a través de la descomposición de árbol. Este algoritmo es el primer paso para resolver este problema en otros grafos en tiempo polinomial en n. A graph G = (V, E) is a discrete structure consisting of the vertex set V and the edge set E. For a graph G, a clique is a subgraph for which an edge connects each vertices pair. A maximal clique in G is a clique that is not a subset of a larger clique in G. The maximal clique enumeration problem consists of enumerating all maximal cliques in G. This problem is N P-Hard when G is arbitrary, and there are no known efficient algorithms that solve it. This work proposes the algorithm DP-CLIQUE, which solves the problem above when the input graph is k-outerplanar. A k-outerplanar graph is a plane graph, such that by removing each vertex that touches the infinite region of the plane that surrounds the graph, and its incident edges, generates a (k − 1)-outerplanar graph. The DP-CLIQUE algorithm employs two algorithms from state of the art. The first algorithm calculates the tree decomposition of a k-outerplanar graph. A tree decomposition is a transformation of the input graph to a tree, in which each of its nodes has unique attributes. Then, the second algorithm generates a nice tree decomposition from the previous decomposition. A nice tree decomposition has additional restrictions that make it easier to process. The algorithm DP-CLIQUE requires O (τ + 1) · n · 2 τ+1 units of time, where n is the number of vertices in the input graph, and τ the treewidth in G. The treewidth of a graph G is a measure that indicates how close G is to a tree. This execution time is polynomial in n if τ is a constant. In particular, τ is a constant when k is a constant. This execution time is equivalent to that of the best-known stateof-the-art algorithm when k is a constant, but it uses an alternative technique. As far as the author of this work knows, the DP-CLIQUE algorithm is the first one that solves the problem mentioned above through tree decomposition. This algorithm is the first step for solving this problem in other graphs on polynomial time in n. | |
| CICESE | |
| 2021 | |
| Tesis de maestría | |
| Español | |
| González Domínguez, F. 2021. Algoritmo de enumeración de cliques maximales en grafos k-outerplanares, usando descomposición de árbol. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 55 pp. | |
| ORDENADORES DIGITALES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| tesis_Francisco González Domínguez_abril 2021.pdf | Versión completa de la tesis | 374.71 kB | Adobe PDF | Visualizar/Abrir |