Open Access. Powered by Scholars. Published by Universities.®
University of Nebraska - Lincoln
Department of Computer Science and Engineering: Dissertations, Theses, and Student Research
Articles 1 - 1 of 1
Full-Text Articles in Computer Engineering
Rectilinear Steiner Tree Construction, Zhiliu Zhang
Rectilinear Steiner Tree Construction, Zhiliu Zhang
Department of Computer Science and Engineering: Dissertations, Theses, and Student Research
The Minimum Rectilinear Steiner Tree (MRST) problem is to find the minimal spanning tree of a set of points (also called terminals) in the plane that interconnects all the terminals and some extra points (called Steiner points) introduced by intermediate junctions, and in which edge lengths are measured in the L1 (Manhattan) metric. This is one of the oldest optimization problems in mathematics that has been extensively studied and has been proven to be NP-complete, thus efficient approximation heuristics are more applicable than exact algorithms.
In this thesis, we present a new heuristic to construct rectilinear Steiner trees (RSTs) with …