Minimizing the density of terminal assignments in layout design
The following problem is studied: each of n given entry terminals positioned at the upper row of a channel has to be assigned to one of m exit terminals positioned at the lower row in such a way that the resulting channel routing problem has minimum density. The authors construct an assignment with minimal density in O(m) time.
scientific article; zbMATH DE number 4018781