Optimal algorithm for river routing with crosstalk constraints

Hai Zhou, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


With the increasing density of VLSI circuits, the interconnection wires are getting packed even closer. This has increased the effect of interaction between these wires on circuit performance and hence, the importance of controlling crosstalk. In this paper, we consider river routing with crosstalk constraints. Given the positions of the pins in a single-layer routing channel and the maximum tolerable crosstalk between each pair of nets, we give a polynomial time algorithm to decide whether there is a feasible river routing solution and produce one with minimum crosstalk whenever the problem is feasible.

Original languageEnglish (US)
Pages (from-to)310-315
Number of pages6
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - 1996
Externally publishedYes
EventProceedings of the 1996 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA
Duration: Nov 10 1996Nov 14 1996

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Optimal algorithm for river routing with crosstalk constraints'. Together they form a unique fingerprint.

Cite this