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

An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut Un algorithme efficace pour extraire un sous-circuit optimal par la coupe minimale

Kengo R. AZEGAMI, Atsushi TAKAHASHI, Yoji KAJITANI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Nous améliorons l'algorithme pour obtenir le graphe min-cut d'un hyper-graphe et montrons une application au problème d'extraction de sous-réseau. Le graphe min-cut est un graphe acyclique orienté dont les coupes dirigées correspondent biunivoquement aux min-cuts de l'hyper-graphe. Alors que l'approche connue échange l'exactitude du graphe de coupe minimale contre une certaine amélioration de la vitesse, l'algorithme que nous proposons en donne un exact sans surcharge de calcul substantielle. En utilisant le graphique min-cut exact, un algorithme exhaustif trouve un sous-circuit optimal qui est extrait du circuit par une min-cut. Grâce à des expériences avec des données industrielles, la méthode proposée a montré des performances suffisantes pour une utilisation pratique.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1301-1308
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
PAPER
Catégories
Technologie de conception VLSI et CAO

Auteurs

Mots-clés

Table des matières