Resumen:
Un clique transversal de un grafo G es un subconjunto de vértices que se intersecan con todos los cliques del grafo G. Es un problema NP-Hard determinar la cardinalidad (τc(G)) del clique transversal de tamaño mínimo para un grafo G. En este trabajo proponemos algoritmos para generar un clique transversal de tamaño mínimo y por consiguiente determinar el valor de τc(G), mejorando algunos resultados de [15]. Los principales algoritmos con los que contribuimos en esta tesis son: 1) Un algoritmo general de tiempo O(n τc(G)−1m τc(G)2) que genera un clique transversal de tamaño mínimo para cualquier grafo G. Este algoritmo es una modificación del algoritmo propuesto en [15] de tiempo O(n 2τc(G)). 2) Un algoritmo robusto de tiempo O(n+m) que genera un clique transversal de tamaño mínimo para cualquier grafo arco-circular sin 3K2 como subgrafo inducido. Este algoritmo primero genera un modelo arco-circular a partir del grafo (cuesta tiempo O(n+m)) y luego lo utiliza para generar un clique transversal mínimo o bien detectar la existencia de un 3K2 como subgrafo inducido del grafo (todo esto cuesta tiempo O(n)). Por lo tanto, si la entrada del algoritmo ya es un modelo arco-circular del grafo, la complejidad total se reduce a O(n). El mejor algoritmo para esta clase de grafos hasta este momento era uno de tiempo O(n4) propuesto en [15]. Al igual que este algoritmo, nuestro algoritmo también es robusto en el sentido que si el grafo de entrada contiene algún 3K2 como subgrafo inducido, o bien el algoritmo genera un clique transversal de tamaño mínimo del grafo o encuentra un subgrado inducido 3K2 en el grafo. 3) Un algoritmo de reconocimiento de tiempo O(nm32) para los grafos arco-circulares sin 3K2. 4) Un algoritmo de tiempo O(τc(G)nmτc(G) 2 −1 (τc(G)+√ m)) que genera un clique transversal de tamaño mínimo para cualquier grafo dualmente cordal G. Este algoritmo emplea la técnica llamada “simplicial augmentation” que fue introducida en [15] para grafos arco-circulares Helly.
Citación:
---------- APA ----------
Arregui, Javier Ignacio. (2011). Algoritmos eficientes para calcular el clique transversal mínimo en grafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000834_Arregui
---------- CHICAGO ----------
Arregui, Javier Ignacio. "Algoritmos eficientes para calcular el clique transversal mínimo en grafos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2011.https://hdl.handle.net/20.500.12110/seminario_nCOM000834_Arregui
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000834_Arregui.pdf
Distrubución geográfica
