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):

Report Date:

1974-03-01

Pagination or Media Count:

46.0

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 On log n operations. Modified author abstract

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE