BIB-VERSION:: CS-TR-v2.0 ID:: STAN//CS-TR-77-626 ENTRY:: June 28, 1995 ORGANIZATION:: Stanford University, Department of Computer Science TITLE:: On the loop switching addressing problem TYPE:: Technical Report AUTHOR:: Yao, Andrew Chi-Chih DATE:: October 1977 PAGES:: 24 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). NOTES:: [Adminitrivia V1/Prg/19950628] END:: STAN//CS-TR-77-626