La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Minimum Cut Linear Arrangement of p-q Dags for VLSI Layout of Adder Trees Disposition linéaire de coupe minimale de car Dags pour la disposition VLSI des arbres additionneurs

Kazuyoshi TAKAGI, Naofumi TAKAGI

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.767-774
Date de publication
1999/05/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières