Recognizing binary Hamming graphs inO(n 2 logn) time

A graphG is called a binary Hamming graph if each vertex ofG 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 thatO(n ² logn) time suffices for deciding whether a givenn-vertex graphG is a binary Hamming graph, and for computing a valid addressing scheme forG provided it exists. This is not far from being optimal asn addresses of lengthn — 1 have to be computed in the worst case.