Optimal Linear Arrangement and Optimal Linear Ordering.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1974
- Accession Number
- AD0779369
Entities
People
- D. Adolphson
- T. C. Hu
Organizations
- University of Wisconsin–Madison