The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Deux algorithmes pour l'arrangement linéaire de coupe minimale d'une classe de graphiques appelée car des jours sont proposés. UN car dag représente le schéma de connexion d'un arbre additionneur, tel que l'arbre de Wallace, et le problème de disposition VLSI d'une tranche de bits d'un arbre additionneur est traité comme le problème d'arrangement linéaire de coupe minimale de son correspondant. car jour. L'un des deux algorithmes est basé sur une programmation dynamique. Il calcule une solution minimale exacte dans nO(1) le temps et l'espace, où n est la taille d'un graphique donné. L'autre algorithme est un algorithme d'approximation qui calcule une solution avec O(Journal n) largeur de coupe. Cela demande O(n enregistrer n) temps.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Kazuyoshi TAKAGI, Naofumi TAKAGI, "Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 5, pp. 767-774, May 1999, doi: .
Abstract: Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_767/_p
Copier
@ARTICLE{e82-a_5_767,
author={Kazuyoshi TAKAGI, Naofumi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees},
year={1999},
volume={E82-A},
number={5},
pages={767-774},
abstract={Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 767
EP - 774
AU - Kazuyoshi TAKAGI
AU - Naofumi TAKAGI
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1999
AB - Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.
ER -