logo móvil

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

Descargar PDF

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


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.

Documentos Relacionados

Temas Virtualpro