Diseño topológico de redes : casos de estudio :"The generalized Steiner problem"and "The Steiner 2-edge-connected subgraph problem"

Abstract

Dado un grafo G=(V,E), una matriz C de costos asociados a las aristas, un subconjunto T de nodos denominados terminales y una matriz R de requerimientos de conexión entre nodos terminales, el "Generalized Steiner Problem" (GSP)consiste en encontrar un subgrafo Gs de G de costo mínimo tal que para todo par de nodos terminales existen al menos Rij caminos de aristas-disjuntas en Gs. Un grafo se dice 2-arista-conexo si entre todo par de nodos existen al menos 2 caminos de aristas disjuntas que los unen. Dos casos particulares de GSP son: encontrar un subgrafo Gs de G 2-arista-conexo de costo mínimo que cubra el conjunto de nodos terminales T, este problema es conocido como "Steiner 2-edge-connected subgraph problem"(STECSP), - encontrar un subgrafo Gs de G de costo mínimo tal que para todo par de nodos terminales existen al menos 2 caminos de aristas disjuntas que los unen, este problema es conocido como "Steiner 2-edge survivable subgraph problem" (STESNP).