Fast Heuristic Algorithms for Rectilinear Steiner Trees

Author:Richards, Dana, Department of Computer ScienceUniversity of Virginia

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

All rights reserved (no additional license for public reuse)
Source Citation:

Richards, Dana. "Fast Heuristic Algorithms for Rectilinear Steiner Trees." University of Virginia Dept. of Computer Science Tech Report (1986).

University of Virginia, Department of Computer Science
Published Date: