On the loop switching addressing problem

[摘要] 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).

[学科分类] 计算机科学（综合）