Anzeige
Erschienen in:
01.04.2016
Optimal weight allocation in rooted trees
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2016
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Some apparently different VLSI circuit design optimization problems can be mapped to the problem of allocating weights (hardware circuits) to the nodes of a tree, such that their total sum (delay) along root-to-leaf paths, or their total product (amplification) along root-to-leaf paths, satisfy given demands (delays or amplifications, respectively) at the tree’s leaves. Node’s weight is shared by all the leaves of its emanating sub-tree. For both the sum and product constraints cases, \(O(n)\) weights allocation algorithms are presented, supplying the demands at the leaves, while the total sum of nodes’ weights (hardware cost) is minimized. When the assignment of the demands to leaves is not predetermined, it is shown that monotonic order of the demands at leaves is optimal for both cases.