Abstract
Minimum spanning tree problem is a very important problem in VLSI CAD. Given n points in a plane, a minimum spanning tree is a set of edges which connects all the points and has a minimum total length. A naive approach enumerates edges on all pairs of points and takes at least Ω(n2) time. More efficient approaches find a minimum spanning tree only among edges in the Delaunay triangulation of the points. However, Delaunay triangulation is not well defined in rectilinear distance. In this paper, we first establish a framework for minimum spanning tree construction which is based on a general concept of spanning graphs. A spanning graph is a natural definition and not necessarily a Delaunay triangulation. Based on this framework, we then design an O(nlogn) sweep-line algorithm to construct a rectilinear minimum spanning tree without using Delaunay triangulation.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the ASP-DAC 2001 |
| Subtitle of host publication | Asia and South Pacific Design Automation Conference 2001 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 192-197 |
| Number of pages | 6 |
| Volume | 2001-January |
| ISBN (Electronic) | 0780366336 |
| DOIs | |
| State | Published - Jan 1 2001 |
| Event | Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 - Yokohama, Japan Duration: Jan 30 2001 → Feb 2 2001 |
Other
| Other | Asia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 |
|---|---|
| Country/Territory | Japan |
| City | Yokohama |
| Period | 1/30/01 → 2/2/01 |
Keywords
- Algorithm design and analysis
- Computational geometry
- Design automation
- Euclidean distance
- Testing
- Tree graphs
- Very large scale integration
- Wire
ASJC Scopus subject areas
- Electrical and Electronic Engineering
- Computer Science Applications
- Computer Graphics and Computer-Aided Design