Accession Number : ADA132572

Title :   An Approximation Algorithm for Manhattan Routing,

Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s) : Baker,Brenda S ; Bhatt,Sandeep N ; Leighton,Frank Thomson

PDF Url : ADA132572

Report Date : Feb 1983

Pagination or Media Count : 18

Abstract : 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.

Descriptors :   *Algorithms, *Routing, *Integrated circuits, Channels, Width, Density, Grids, Nets, Terminals, Wire, Tracks, Connectors

Subject Categories : Electrical and Electronic Equipment

Distribution Statement : APPROVED FOR PUBLIC RELEASE