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
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.
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
Kengo R. AZEGAMI, Atsushi TAKAHASHI, Yoji KAJITANI, "An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 5, pp. 1301-1308, May 2001, doi: .
Abstract: We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the sub-network extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_5_1301/_p
Copier
@ARTICLE{e84-a_5_1301,
author={Kengo R. AZEGAMI, Atsushi TAKAHASHI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut},
year={2001},
volume={E84-A},
number={5},
pages={1301-1308},
abstract={We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the sub-network extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.},
keywords={},
doi={},
ISSN={},
month={May},}
Copier
TY - JOUR
TI - An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1301
EP - 1308
AU - Kengo R. AZEGAMI
AU - Atsushi TAKAHASHI
AU - Yoji KAJITANI
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2001
AB - We improve the algorithm to obtain the min-cut graph of a hyper-graph and show an application to the sub-network extraction problem. The min-cut graph is a directed acyclic graph whose directed cuts correspond one-to-one to the min-cuts of the hyper-graph. While the known approach trades the exactness of the min-cut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact min-cut graph, an exhaustive algorithm finds an optimal sub-circuit that is extracted by a min-cut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.
ER -