Resumen de Els arbres de steiner: obtencio i propietats
La tesis esta dedicada a estudiar el problema de steiner en sus tres variantes: usando la metrica euclidea usando la metrica rectilinea y considerando un grafo simetrico, se presentan los metodos tanto exactos como heuristicos desarrollados hasta el presente asi como las propiedades que verifica la solucion en cada uno de los casos considerados. Dado el caracter de problema np-completo se han desarrolladovarios algoritmos heuristicos que abordan satisfactoriamente el problema en los dos ultimos casos citados. Asimismo se han obtenido nuevas cotas superiores parala longitud del arbol solucion en el caso de la metrica l2 en el interior de una region finita -circulo de radio r- y para el arbol minimal en el caso de lametrica l1 tomando como region el cuadrado de lado igual a 1. Finalmente se ha hecho una generalizacion del problema que contempla la posibilidad de aumentar el grado de conectividad de los vertices que forman la solucion. El proceso pasa por preveer que haya k caminos disjuntos de aristas-vertices entre cada pareja de vertices a interconectar. Los dos algoritmos desarrollados contemplan el caso k=2. Palabras clave: steiner problem minimum spanning tree graph theory algorithms.
