Another approach to the Steiner Problem in Graphs and its generalization

• J.M Basart ^[1] ; J. Rifá ^[1]
  1. [1] Universitat Autònoma de Barcelona

     Universitat Autònoma de Barcelona

     Barcelona, España

     
• Localización: Mini and Microcomputers and their applications / Emilio Luque Fadón (ed. lit.) , 1988, págs. 304-308
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • A polynomial -time heuristic algorithm for solving the Steiner Problem in Graphs is explained. It is based on a progressive imporvement of the minimum spanning tree associated to the graph, by means of effiecient keeper -path substitions in its edge set.

    The Generalized Stainer Problem in Graphs adds some edge/vertex path connectivity constraints to the set of vertices to be linked.

    Two methods for the biconnectivity case have been developed wich can be used in both:edge and vertex connectivity.