Calcular el gráfico átomo de un gráfico y el gráfico de unión unión de un hipergrafo
Autores: Berry, Anne; Simonet, Geneviève
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
Categoría
Ingeniería y Tecnología
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 16
Citaciones: Sin citaciones
El grafo átomo de un grafo es un grafo cuyos vértices son los átomos obtenidos por la descomposición del separador mínimo de cliques de este grafo, y cuyos bordes son los bordes de todos los árboles de átomos posibles de este grafo. Proporcionamos dos algoritmos eficientes para calcular este grafo átomo, con una complejidad en tiempo, donde es el número de vértices de , es el número de sus bordes, es el número de bordes del complemento de , y , también denotado por en la literatura, es un número real, tal que es la complejidad de tiempo conocida más óptima para la multiplicación de matrices, cuyo valor actual es 2,3728596. Esta complejidad de tiempo no es más que la complejidad de tiempo de calcular los átomos en el caso general. Extendemos nuestros resultados a hipergrafos -acíclicos, que son hipergrafos que tienen al menos un árbol de unión, siendo un árbol de unión de un hipergrafo definido por sus hiperbordes de la misma manera que un árbol de átomos de un grafo se define por sus átomos. Introducimos la noción de grafo de unión de unión, que es la unión de todos los árboles de unión posibles; aplicamos nuestros algoritmos para grafos átomos para calcular eficientemente los grafos de unión de unión.
Descripción
El grafo átomo de un grafo es un grafo cuyos vértices son los átomos obtenidos por la descomposición del separador mínimo de cliques de este grafo, y cuyos bordes son los bordes de todos los árboles de átomos posibles de este grafo. Proporcionamos dos algoritmos eficientes para calcular este grafo átomo, con una complejidad en tiempo, donde es el número de vértices de , es el número de sus bordes, es el número de bordes del complemento de , y , también denotado por en la literatura, es un número real, tal que es la complejidad de tiempo conocida más óptima para la multiplicación de matrices, cuyo valor actual es 2,3728596. Esta complejidad de tiempo no es más que la complejidad de tiempo de calcular los átomos en el caso general. Extendemos nuestros resultados a hipergrafos -acíclicos, que son hipergrafos que tienen al menos un árbol de unión, siendo un árbol de unión de un hipergrafo definido por sus hiperbordes de la misma manera que un árbol de átomos de un grafo se define por sus átomos. Introducimos la noción de grafo de unión de unión, que es la unión de todos los árboles de unión posibles; aplicamos nuestros algoritmos para grafos átomos para calcular eficientemente los grafos de unión de unión.