Dim Sum: Light Clock Tree by Small Diameter Sum
Gengjie Chena and Evangeline F. Y. Youngb
The Chinese University of Hong Kong
agjchen@cse.cuhk.edu.hk
bfyyoung@cse.cuhk.edu.hk
ABSTRACT
By retrospecting the classical deferred-merge embedding (DME) algorithm, we found an intrinsic relationship between the zero-skew tree (ZST) problem and the hierarchical clustering (HC) problem. To be more specific, the wire length of a ZST is proved a linear function of the sum of diameters of its corresponding HC. With this new insight, an effective O(n log n)-time O(1)-approximation algorithm and an optimal dynamic programming for ZST are designed. Using the ZST construction black box and a linear-time optimal tree decomposition algorithm, an improved algorithm for constructing the bounded-skew tree (BST) is derived. In the experiment, our approach shows superior wire length compared with previous methods for both ZST and BST.
