Recognizing binary Hamming graphs in O(n^2 logn) time

F. Aurenhammer, J. Hagauer

Research output: Contribution to journalArticlepeer-review


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 2 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.
Original languageEnglish
Pages (from-to)387-395
JournalMathematical Systems Theory
Issue number28
Publication statusPublished - 1995

Cite this