
Summary: The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications, including network multicasting [\textit{G. N. Rouskas} and \textit{I. Baldine}, IEEE J. Select. Areas Commun. 15, 346-356 (1997)] and VLSI clock routing [\textit{H. Bakoglu}, Circuits, Interconnections, and Packaging for VSLI, Addison-Wesley, Reading, MA 1990, \textit{A. B. Kahng} and \textit{G. Robins}, On Optimal Interconnections for VSLI, Kluwer Academic Publishers, Norwell, MA (1995)]. In these applications edge weights represent propagation delays, and a signal generated at the root should be received by multiple recipients located at the leaves (almost) simultaneously. The objective is to find zero- or bounded-skew trees of minimum total weight, since the weight of the tree is directly proportional to the amount of resources (bandwidth and buffers for network multicasting, power and chip area for clock routing in VLSI) that must be allocated to the tree. Charikar et al. in [Proceedings of the Tenth ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD 1999, ACM, New York, 177-184 (1999)] have recently proposed the first strongly polynomial algorithms with proven constant approximation factors, \(2e\approx 5.44\) and 16.86, for finding minimum weight zero- and bounded-skew trees, respectively. In this paper we introduce a new approach to these problems, based on zero-skew ``stretching'' of spanning trees, and obtain algorithms with improved approximation factors of 4 and 14. For the case when tree nodes are points in the plane and edge weights are given by the rectilinear metric our algorithms find zero- and bounded-skew trees of length at most 3 and 9 times the optimum. This case is of special interest in VLSI clock routing. An important feature of our algorithms is their practical running time, which is asymptotically the same as the time needed for computing the minimum spanning tree.
VLSI physical design, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), Graph algorithms (graph-theoretic aspects), Steiner trees, clock routing, Analysis of algorithms, approximation algorithms, Approximation algorithms, Trees
VLSI physical design, Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.), Graph algorithms (graph-theoretic aspects), Steiner trees, clock routing, Analysis of algorithms, approximation algorithms, Approximation algorithms, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
