**F. Aurenhammer and J. Hagauer**

A graph is called a binary Hamming graph if each vertex of can be
assigned a binary address of fixed length such that the Hamming distance
between two addresses equals the length of a shortest path between the
corresponding vertices. It is shown that time suffices for
deciding whether a given -vertex graph is a binary Hamming graph, and
for computing a valid addressing scheme for provided its existence. This
is not far from being optimal as addresses of length have to be
computed in the worst case.