Next: Routing Problems Up: Cuts and Connectivity Previous: MINIMUM STRONG CONNECTIVITY AUGMENTATION Index

### MINIMUM BOUNDED DIAMETER AUGMENTATION

- INSTANCE: Graph , positive integer D<|V|.

- SOLUTION: 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.

- MEASURE: Cardinality of the augmenting set, i.e., |E'|.

- Bad News: As hard to approximate as MINIMUM SET COVER [337].

- Comment: Variation in which the size of the augmenting set is bounded by D and the problem is to minimize the diameter is approximable within [337].