Resumen de Another approach to the Steiner Problem in Graphs and its generalization

J.M. Basart Arraut, Josep Rifà i Coma

• 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.