| iven a 2-connected graph with edge weights and a subset of distinguished vertices, the 2-Connected Steiner Subgraph Problem is to find a minimum weight 2-connected subgraph that spans all of the distinguished vertices. Many survivable network design problems having applications in communications networks, water- and electric-supply networks, transportation networks, and networks arising in the routing of AGV and VLSI designs can be modeled as 2-Connected Steiner Subgraph Problem.;The 2-Connected Steiner Subgraph Problem is NP-hard. The well-known Traveling Salesman Problem is a closely related problem in which all the vertices of the graph are distinguished, and the desired subgraphs are restricted to be cycles.;This dissertation presents new polyhedral as well as algorithmic results for the 2-Connected Steiner Subgraph Problem posed on special classes of graphs. The 2-connected-spanning-subgraph polyhedra for series-parallel and... |
