logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro