Accession Number : AD0779369

Title :   Optimal Linear Arrangement and Optimal Linear Ordering.

Descriptive Note : Technical summary rept.,


Personal Author(s) : Adolphson,D. ; Hu,T. C.

Report Date : MAR 1974

Pagination or Media Count : 46

Abstract : Consider a set of n pins and a required number of wire connections between each pair of the pins. The problem is to put the n pins into n holes such that the total wire length is a minimum. The holes are all in a line with adjacent holes at unit distance apart. The authors can abstract the pins and wire connections as a graph G with n nodes and numbers associated with the arcs. For an arbitrary G, a lower bound is established on the total wire length. If G is a rooted tree, an algorithm is presented which requires O(n log n) operations. (Modified author abstract)

Descriptors :   *Network flows, Matrices(Mathematics), Graphics, Theorems

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE