MINIMUM METRIC DIMENSION

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

INSTANCE: Graph $G=\left(V,E\right)$ .
SOLUTION: A metric basis for G, i.e., a subset $V' \subseteq V$ such that for each pair $u,v \in V$ there is a $w\in V'$ 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., $\vert V'\vert$ .
Good News: Approximable within $O(\log \vert V\vert)$ [313].
Garey and Johnson: GT61

Viggo Kann
2000-03-20