Eficiente mantenimiento de árboles de expansión mínima en grafos ponderados no dirigidos dinámicos
Autores: Luo, Mao; Qin, Huigang; Wu, Xinyun; Xiong, Caiquan; Xia, Dahai; Ke, Yuanzhi
Idioma: Inglés
Editor: MDPI
Año: 2024
Acceso abierto
Artículo científico
2024
Eficiente mantenimiento de árboles de expansión mínima en grafos ponderados no dirigidos dinámicos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Algoritmo de árbol de expansión mínima
Grafos dinámicos
Ponderado
No dirigido
De Kruskal.
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 19
Citaciones: Sin citaciones
Este documento presenta un algoritmo para mantener eficazmente el árbol de expansión mínimo en grafos ponderados no dirigidos dinámicos. El algoritmo actualiza eficientemente el árbol de expansión mínimo cuando cambia la estructura del grafo subyacente. Al identificar la porción del árbol original que se puede preservar en el árbol actualizado, nuestro algoritmo evita recalcular el árbol de expansión mínimo desde cero. Proporcionamos una prueba de corrección para el algoritmo propuesto y analizamos su complejidad temporal. En escenarios generales, la complejidad temporal de nuestro algoritmo es comparable a la del algoritmo de Kruskal. Sin embargo, los resultados experimentales demuestran que nuestro algoritmo supera al enfoque de recalcular el árbol de expansión mínimo utilizando el algoritmo de Kruskal, especialmente en grafos dinámicos de tamaño mediano y grande donde el grafo experimenta cambios iterativos.
Descripción
Este documento presenta un algoritmo para mantener eficazmente el árbol de expansión mínimo en grafos ponderados no dirigidos dinámicos. El algoritmo actualiza eficientemente el árbol de expansión mínimo cuando cambia la estructura del grafo subyacente. Al identificar la porción del árbol original que se puede preservar en el árbol actualizado, nuestro algoritmo evita recalcular el árbol de expansión mínimo desde cero. Proporcionamos una prueba de corrección para el algoritmo propuesto y analizamos su complejidad temporal. En escenarios generales, la complejidad temporal de nuestro algoritmo es comparable a la del algoritmo de Kruskal. Sin embargo, los resultados experimentales demuestran que nuestro algoritmo supera al enfoque de recalcular el árbol de expansión mínimo utilizando el algoritmo de Kruskal, especialmente en grafos dinámicos de tamaño mediano y grande donde el grafo experimenta cambios iterativos.