Efficient minimum spanning tree construction without Delaunay triangulation [VLSI CAD]

Hai Zhou, N. Shenoy, W. Nicholls

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

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 languageEnglish (US)
Title of host publicationProceedings of the ASP-DAC 2001
Subtitle of host publicationAsia and South Pacific Design Automation Conference 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages192-197
Number of pages6
Volume2001-January
ISBN (Electronic)0780366336
DOIs
StatePublished - Jan 1 2001
EventAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001 - Yokohama, Japan
Duration: Jan 30 2001Feb 2 2001

Other

OtherAsia and South Pacific Design Automation Conference 2001, ASP-DAC 2001
CountryJapan
CityYokohama
Period1/30/012/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

Fingerprint Dive into the research topics of 'Efficient minimum spanning tree construction without Delaunay triangulation [VLSI CAD]'. Together they form a unique fingerprint.

Cite this