An Approximation Algorithm for Manhattan Routing

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 flux. We show that flux, like density, is a lower bound on channel width. In addition, we present a linear-time algorithm whi...

Full description

Bibliographic Details
Main Authors: Baker, Brenda S., Bhatt, Sandeep N., Leighton, Frank Thomson
Published: 2023
Online Access:https://hdl.handle.net/1721.1/149048