Resumen del trabajo fin de master

En este trabajo se hará una revisión bibliográfica del problema del Árbol de Steiner. Se trata de una generalización del problema clásico del árbol de mínimo coste donde se desea encontrar la red que conecta a coste (distancia) mínima un conjunto de nodos con una fuente que suministra un determinado recurso. En el problema de Steiner cabe la posibilidad de generar nuevos nodos intermedios, llamémosles nodos públicos, que sirven como intermediarios en las conexiones y que por lo tanto disminuirían en mayor medida el coste (distancia) total de conexión de todos los nodos. La inclusión de estos nodos públicos, provoca que el problema se vuelva NP duro y que sean necesarias heurísticas para su resolución.