River Routing with a Generalized Model

摘要

Traditional restrictions on river routing confine the connecting wires to the channel between the terminal rows. In (J. Comput. System Sci.28(1984), 420–438) these restrictions were somewhat relaxed, thereby permitting a limited type of routing outside of the channel. Here, the constraints are further relaxed to allow for a new class of “generalized” river routings. We show that this new class of generalized river routings contains routings that are significantly more compact than those previously considered. In addition, we give a fast polynomial time algorithm for producing optimal routings in this new class. The run time of our algorithm is the best possible and is identical to the time required to produce optimal river routings under the traditional model.