Recognizing binary Hamming graphs in $O(n^{2} \log n)$ time

F. Aurenhammer and J. Hagauer

Abstract:

A graph $G$ is called a binary Hamming graph if each vertex of $G$ 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 $O(n^2 \log n)$ time suffices for deciding whether a given $n$-vertex graph $G$ is a binary Hamming graph, and for computing a valid addressing scheme for $G$ provided its existence. This is not far from being optimal as $n$ addresses of length $n-1$ have to be computed in the worst case.

Reference: F. Aurenhammer and J. Hagauer. Recognizing binary Hamming graphs in $O(n^{2} \log n)$ time. Mathematical Systems Theory, 28:387-395, 1995. [IIG-Report-Series 273, TU Graz, Austria, 1989].