Optimal Linear Ordering

Consider a set of n pins and n (n - 1) /2 specified numbers of wire connections between all pairs of the n pins There are also n holes all in a line with adjacent holes at unit distances apart. The problem is to put the n pins into the n holes such that the total wire length is a minimum. We can abstract the pins and wire connections as a graph G with n nodes and numbers associated with the arcs. For an arbitrary G, we establish a lower bound on the total wire length. If G is a rooted tree, an algorithm is presented which requires O (n n) operations.