Next: MINIMUM TREE WIDTH Up: Miscellaneous Previous: MINIMUM POINT-TO-POINT CONNECTION Index

### MINIMUM METRIC DIMENSION

- INSTANCE: Graph .

- SOLUTION: A metric basis for G, i.e., a subset such that for each pair there is a such that the length of the shortest path from u to w is different from the length of the shortest path from v to w.

- MEASURE: The cardinality of the metric basis, i.e., |V'|.

- Good News: Approximable within [296].

- Garey and Johnson: GT61