Optimal Linear Ordering

Abstract

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\log n} )$ operations.