Next: MINIMUM TREE WIDTH
Up: Miscellaneous
Previous: MINIMUM POINT-TO-POINT CONNECTION
  Index
- 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.,
.
- Good News:
Approximable within
[313].
- Garey and Johnson: GT61
Viggo Kann
2000-03-20