- INSTANCE:
Graph
, edge costs
, degree bounds
, requirements
- SOLUTION:
A subgraph
of
which contains for each pair of vertices
at least
edge-disjoint paths from
to
and such that
for all
,
- COST FUNCTION:
- OBJECTIVE:
Minimize.
*Approx.:*There exists an algorithm which constructs a subgraph of cost at most times the optimum cost such that satisfies all the connectivity requirements and such that , where [82].*Comment:*There exists a bicriteria approximation algorithm for Degree Bounded Survivable Network Design with element-connectivity requirements, where the paths satisfying the connectivity requirements have to be element disjoint [45]. For the Degree Bounded Survivable Network Design problem with node-connectivity requirements, there exists a bicriteria approximation algorithm, where is the maximum connectivity requirement of any pair [45].