Ir al contenido

Documat


Els arbres de steiner: obtencio i propietats

  • Autores: Josep M. Basart i Muñoz Árbol académico
  • Directores de la Tesis: Llorenç Huguet Rotger (dir. tes.) Árbol académico
  • Lectura: En la Universitat Autònoma de Barcelona ( España ) en 1988
  • Idioma: catalán
  • Tribunal Calificador de la Tesis: Claudi Alsina Català (presid.) Árbol académico, Miguel Ángel Fiol Mora (secret.) Árbol académico, Jordi Aguiló Llobet (voc.) Árbol académico, Emilio Luque Fadón (voc.) Árbol académico, Gerard Cohen (voc.) Árbol académico
  • Texto completo no disponible (Saber más ...)
  • Resumen
    • 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.


Fundación Dialnet

Mi Documat

Opciones de tesis

Opciones de compartir

Opciones de entorno