Next: MINIMUM TREE WIDTH
Previous: MINIMUM POINT-TO-POINT CONNECTION
A metric basis for G, i.e., a subset
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.
The cardinality of the metric basis, i.e., .
- Good News:
- Garey and Johnson: GT61