Anzeige
Erschienen in:
1994 | ReviewPaper | Buchkapitel
On Steiner minimal trees in grid graphs and its application to VLSI routing
verfasst von : Michael Kaufmann, Shaodi Gao, K. Thulasiraman
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we present an algorithm for Steiner minimal trees in grid graphs with all terminals located on the boundary of the graph. The algorithm runs in O(k2*mink2 log k, n) time, where k and n are the numbers of terminals and vertices of the graph, respectively. It can handle non-convex boundaries and is the fastest known for this case. We also describe a new approach to the homotopic routing problem in VLSI layout design, which applies our Steiner tree algorithm to construct minimum-length wires for multi-terminal nets.