Channel Density Minimization by Pin Permutation | Zendy

Yang Cai | Zendy; Martin D. F. Wong | Zendy; Jason Cong | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Channel Density Minimization by Pin Permutation

Author(s) -

Yang Cai,

Martin D. F. Wong,

Jason Cong

Publication year - 1994

Publication title -

vlsi design

Language(s) - English

Resource type - Journals

eISSN - 1065-514X

pISSN - 1026-7123

DOI - 10.1155/1994/68279

Subject(s) - permutation (music) , minification , channel (broadcasting) , algorithm , computer science , electronic circuit , mathematics , mathematical optimization , engineering , telecommunications , electrical engineering , physics , acoustics

We present in this paper a linear time optimal algorithm for minimizing the density of a channel (with exits) bypermuting the terminals on the two sides of the channel. This compares favorably with the previously knownnear-optimal algorithm presented in [6] that runs in superlinear time. Our algorithm has important applicationsin hierarchical layout design of intergrated circuits. We also show that the problem of minimizing wire length bypermuting terminals is NP-hard in the strong sense

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research