Minimizing channel density with movable terminals
Ronald I. Greenberg, Jau-Der Shih · 2002
Algorithms to minimize density for channels with terminals that are movable subject to certain constraints are given. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L, respectively, where L is the channel length and n is the number of terminals.>