Propagation of trust and distrust
R. Guha, Prabhakar Raghavan, et al.
WWW 2004
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.
R. Guha, Prabhakar Raghavan, et al.
WWW 2004
Nikhil Bansal, Moses Charikar, et al.
SODA 2005
T.S. Jayram, Ravi Kumar, et al.
STOC 2003
Parikshit Gopalan, T.S. Jayram, et al.
SODA 2007