Report Number: CS-TR-77-626
Institution: Stanford University, Department of Computer Science
Title: On the loop switching addressing problem
Author: Yao, Andrew Chi-Chih
Date: October 1977
Abstract: The following graph addressing problem was studied by Graham and Pollak in devising a routing scheme for Pierce's Loop Switching Network. Let G be a graph with n vertices. It is desired to assign to each vertex $v_i$ an address in ${{0,1,*}}^\ell$, such that the Hamming distance between the addresses of any two vertices agrees with their distance in G. Let N(G) be the minimum length $\ell$ for which an assignment is possible. It was shown by Graham and Pollak that N(G) $\leq m_G$(n-1), where $m_G$ is the diameter of G. In the present paper, we shall prove that N(G) $\leq 1.09(lg m_G$)n + 8n by an explicit construction. This shows in particular that any graph has an addressing scheme of length O(n log n).
http://i.stanford.edu/pub/cstr/reports/cs/tr/77/626/CS-TR-77-626.pdf