Approximation Algorithm for Manhattan Routing.

摘要

Channel routing plays a central role in the development of automated layout systems for integrated circuits. One of the most common models for channel routing is known as Manhattan routing. In Manhattan routing, the channel consists of a 2-layer rectangular grid of columns and tracks(rows). Terminals are located in the top layer of the top and bottom tracks at points where the tracks intersect a column. A set of terminals to be connected is called a net. Nets containing r terminals (r must always be larger than 1) are called r-point nets. The object of the channel routing problem is to connect the terminals in each net with wires in a way which minimizes the width of the channel. Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, the authors identify a second important measure of difficulty, which is called flux. They show that flux, like density, is a lower bound on channel width. Also presented is a linear-time algorithm which routes any multipoint net Manhattan routing problem with density d and flux f in a channel of width 2d+O(f). (For 2-point nets, the bound is d+O(f).) Thus it is shown that Manhattan routing is one of the NP-complete problems for which there is a provably good approximation algorithm.