On Terminal Assignments That Minimize the Density
Mikhail J. Atallah, Susanne E. Hambrusch · Purdue e-Pubs (Purdue University System) · 1984
Terminal assignment problems are placement problems in channel routing in which each one of n entry terminals on one side of the channel is assigned to one of m exit terminals on the other side of the channel.We study solutions to terminal assignment problems that minimize the density.a cost measure closely related to the minimum channel width needed to wire the resulting channel routing problem.We present a new characterization of the optimal achievable density that leads to efficient algorithms for a number of terminal assignment problems.and we show that other assignment problems are NP.bard.