River routing in VLSI

摘要

A common framework for solving several VLSI river routing problems is developed. The main result of this paper is an O(n) time algorithm for the optimum offset problem. This improves upon the best previously known O(n log n) time bound. A new reduction technique called halving is used to achieve this result. A variety of other applications of the halving technique are also mentioned. Algorithms for the minimum area, minimum longest wire length, and minimum total wire length problems are also given that take O(n2) time.