Optimal layout of hexagonal minimum spanning trees in linear time [VLSI]

With the advent of deep sub-micron technology, gate delays are much smaller than wire delays. As a result, hexagonal Steiner minimum trees have received extensive study recently because of their applications in VLSI physical design. Just like its rectilinear and Euclidean counterparts, the hexagonal Steiner minimum tree problem can be shown to be NP-hard. Therefore polynomial time approximation algorithms are of great interest. In a recent paper, Lin, Xue and Zhou (1999) proposed a quadratic time algorithm to compute an optimal layout of a hexagonal minimum spanning tree with attractive computational results. In this paper, we present an improved linear time algorithm for computing an optimal layout of a hexagonal minimum spanning tree