Ziv Bar-Yossef, T.S. Jayram, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
An important problem in VLSI design is distributing a clock signal to synchronous elements in a VLSI circuit so that the signal arrives at all elements simultaneously. The signal is distributed by means of a clock routing tree rooted at a global clock source. The difference in length between the longest and shortest root-leaf path is called the skew of the tree. The problem is to construct a clock tree with zero skew (to achieve synchronicity) and minimal sum of edge lengths (so that circuit area and clock tree capacitance are minimized). We give the first constant-factor approximation algorithms for this problem and its variants that arise in the VLSI context. For the zero skew problem in general metric spaces, we give an approximation algorithm with a performance guarantee of 2e. For the L 1 version on the plane, we give an (8/ ln 2)-approximation algorithm.
Ziv Bar-Yossef, T.S. Jayram, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
Ziv Bar-Yossef, Ravi Kumar, et al.
WWW 2004
Ronald Fagin, Anna R. Karlin, et al.
Annals of Applied Probability
Ronald Fagin, Ravi Kumar, et al.
SIAM Journal on Discrete Mathematics