A fast approach to the minimum rectilinear Steiner tree (MRST) problem is presented. The
method yields results that reduce wire length by up to 2% to 3% over the previous methods …

On Optimal Interconnections for VLSI describes, from a geometric perspective, algorithms for
high-performance, high-density interconnections during the global and detailed routing …

From the Publisher: This text treats the physical design of very large scale integrated circuits
gradually and systematically. It examines the design problem and the design process with …

Predictable routing is the concept of using prespecified patterns to route a net. By doing this,
we allow an more accurate prediction mechanism for metrics such as congestion and …

This paper presents a new model for VLSI routing in the presence of obstacles, that
transforms any routing instance from a geometric problem into a graph problem. It is the first …

The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring
estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and …

A hierarchical approach to Steiner tree construction in lambda-geometry is proposed. The
algorithm runs in time O (n log n) and the length of the constructed tree is at most (sigma/cos …

Virtually all previous methods for the rectilinear Steiner tree problem begin with a minimum
spanning tree topol-ogy and rearrange edges to induce Steiner points. This paper gives a …

This chapter addresses several variations of the corresponding fundamental Steiner minimal
tree problem, where a given set of pins is to be connected using minimum total wirelength. It …

We devised an efficient and accurate estimation of the rectilinear Steiner minimal tree (SMT),
which is an essential building block for on-line and posteriori interconnect prediction. We …