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...
Main Authors: | , , |
---|---|
Published: |
2023
|
Online Access: | https://hdl.handle.net/1721.1/149048 |