Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao zbMATH Openarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
SIAM Journal on Discrete Mathematics
Article . 2001 . Peer-reviewed
Data sources: Crossref
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Practical Approximation Algorithms for Zero- and Bounded-Skew Trees

Practical approximation algorithms for zero- and bounded-skew trees
Authors: Zelikovsky, Alexander Z.; Mandoiu, Ion I.;

Practical Approximation Algorithms for Zero- and Bounded-Skew Trees

Abstract

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.

Keywords

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

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
6
Average
Top 10%
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!