Abstract
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 language | English |
---|---|
Pages (from-to) | 387-395 |
Journal | Mathematical Systems Theory |
Issue number | 28 |
DOIs | |
Publication status | Published - 1995 |