Accession Number : AD0779369
Title : Optimal Linear Arrangement and Optimal Linear Ordering.
Descriptive Note : Technical summary rept.,
Corporate Author : WISCONSIN UNIV MADISON MATHEMATICS RESEARCH CENTER
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