LCS Publication Details
Publication Title: AN APPROXIMATION ALGORITHM FOR MANHATTAN ROUTING
Publication Author: Baker, Brenda S.
Additional Authors: Bhatt, Sandeep N. and Leighton, Frank T.
LCS Document Number: MIT-LCS-TM-238
Publication Date: 2-1-1983
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
Density has long been known to be an important measure of difficulty for Manhattan routing. In this paper, we identify a second important measure of difficulty, which we call fluz. We show that flux, like density, is a lower bound on channel width. In addition, we present a linear-time algorithm which routes any multipoint net Manhattan routing problem with density d and flux f in a channel of width 2d +0(f). (For 2-point nets, the bound is d +0(f).) Thus we show that Manhattan routing is one of the NP-complete problems for which there is a provably good approximation algorithm.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.