Next: Routing Problems
Up: Cuts and Connectivity
Previous: MINIMUM STRONG CONNECTIVITY AUGMENTATION
positive integer .
An augmenting set E' for G, i.e., a set E' of unordered
pairs of vertices from V, such that
has diameter D, i.e., the maximum distance of any pair of vertices is
at most D.
Cardinality of the augmenting set, i.e., .
- Bad News:
As hard to approximate as MINIMUM SET COVER .
Variation in which the size of the augmenting set is bounded by D and
the problem is to minimize the diameter is approximable within