Crosstalk-constrained maze routing based on Lagrangian relaxation

Hai Zhou, D. F. Wong

Research output: Contribution to conferencePaperpeer-review


With the increasing density of VLSI circuits, interconnection wires are getting packed even closer. This has increased the effect of interaction between wires on circuit performance and hence, the importance of controlling crosstalk. Maze routing is a robust and general approach which can be used in many situations including multi-layer interconnections. In this paper, we consider crosstalk avoidance in maze routing. The crosstalk-constrained maze routing problem is first formulated. Then we show it is equivalent to the multi-constrained shortest path problem and is strongly NP-complete. Based on the Lagrangian relaxation technique, an effective heuristic algorithm is designed to solve the problem.

Original languageEnglish (US)
Number of pages6
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 International Conference on Computer Design - Austin, TX, USA
Duration: Oct 12 1997Oct 15 1997


OtherProceedings of the 1997 International Conference on Computer Design
CityAustin, TX, USA

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Crosstalk-constrained maze routing based on Lagrangian relaxation'. Together they form a unique fingerprint.

Cite this