Diseño topológico de redes terminales

Abstract

En este trabajo se aborda el problema de la forma de conectar un conjunto de terminales a la unidad de procesos central. La resolución de este problema lleva a la determinación de un árbol de mínima extensión (minimum spanning tree) con restricciones. Se estudian los principales algoritmos en uso para así poder encontrar la filosofía que tuvieron algunos autores para resolver el problema. También se hizo la implementación computacional de estos algoritmos. A continuación, se propone un algoritmo heurístico basado en el algoritmo de Essau-Williams, con una búsqueda de conexión desde la periferia hacia el nodo central. La ventaja del algoritmo propuesto respecto del original es una disminución de tiempo para llegar a la solución, resolviendo simultáneamente las situaciones conflictivas del mismo.