Item Details

Print View

Fast Heuristic Algorithms for Rectilinear Steiner Trees

Richards, Dana
Format
Report
Author
Richards, Dana
Abstract
A fundamental problem in circuit design is how to connect It points in the plane, to make them electrically common using the least amount of wire. The tree formed, a Steiner tree, is usually constructed with respect to the rectilinear metric. The problem is known to be NP~comp1ete; an extensive review of proposed heuristics is given. An early algorithm by Hanan is shown to have an O(n1ogn) time implementation using computational geometry techniques. The algorithm can be modified to do sequential searching in 0(n2) total time. However it shown that the latter approach runs in 0(n3'2) expected time, for n points selected from an m Xm grid. Empirical results are presented for problems up to 10000 points. Note: Abstract extracted from PDF file via OCR
Language
English
Date Received
2012-10-29
Published
University of Virginia, Department of Computer Science, 1986
Published Date
1986
Rights
All rights reserved (no additional license for public reuse)
Collection
Libra Open Repository

Availability

Access Online