Rectilinear minimum spanning tree
In graph theory, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane (or more generally in–ℝd) is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.
Properties and algorithms
|This section is empty. You can help by adding to it. (January 2011)|
The problem commonly arises in physical design of electronic circuits. In modern high-density integrated circuits wire routing is performed by wires which consist of segments running horizontally in one layer of metal and vertically in another metal layer. As a result, the wire length between two points is naturally measured with rectilinear distance. Although the routing of a whole net with multiple nodes is better represented by the rectilinear Steiner tree, the RMST provides a reasonable approximation and wire length estimate.
- F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|