A Language for Describing Rectilinear Steiner Tree Configurations

We propose a language that can be used to describe configurations of rectilinear Steiner trees. Given a set of points in a plane indexed by integer coordinates, the execution of a pattern-description in our language will list a number of Steiner trees spanning the points. The Steiner trees that are...

Full description

Saved in:
Bibliographic Details
Main Authors: Ng, A.P.-C., Raghavan, P., Thompson, C.D.
Format: Conference Proceeding
Language:English
Subjects:
Circuit simulation
Computer science
Fabrication
Integrated circuit interconnections
Polynomials
Printed circuits
Routing
Steiner trees
Very large scale integration
Wires
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a language that can be used to describe configurations of rectilinear Steiner trees. Given a set of points in a plane indexed by integer coordinates, the execution of a pattern-description in our language will list a number of Steiner trees spanning the points. The Steiner trees that are produced will be used as input to a linear-program type global router for VLSI gate-arrays [10]. Other applications for our language include routing printed circuit boards and generating Steiner tree configurations for simulated-annealing type global routers [11].
ISSN:0738-100X
DOI:10.1109/DAC.1986.1586159