Delay-related secondary objective for rectilinear Steiner trees

Sven Peyer, Martin Zachariasen, David Grove Jørgensen

Research output: Contribution to journalArticlepeer-review


The rectilinear Steiner tree problem in the plane is to construct a minimum-length tree interconnecting a set of points (called terminals) consisting of horizontal and vertical line segments only. Rectilinear Steiner minimum trees (RSMTs) can today be computed quickly for realistic instances occurring in VLSI design. However, interconnect signal delays are becoming increasingly important in modern chip designs. Therefore, the length of paths or direct delay measures should be taken into account when constructing rectilinear Steiner trees. We consider the problem of finding an RSMT that — as a secondary objective — minimizes a signal delay related objective. Given a source (one of the terminals) we give some structural properties of RSMTs for which the weighted sum of path lengths from the source to the other terminals is minimized. Also, we present exact and heuristic algorithms for constructing RSMTs with weighted sum of path lengths or Elmore delays secondary objectives. Computational results for industrial designs are presented.
Original languageEnglish
Pages (from-to)271-298
Number of pages28
JournalDiscrete Applied Mathematics
Issue number2-3
Publication statusPublished - 2004


  • rectilinear steiner trees
  • VLSI design
  • secondary objectives


Dive into the research topics of 'Delay-related secondary objective for rectilinear Steiner trees'. Together they form a unique fingerprint.

Cite this