IEICE TRANSACTIONS on Fundamentals
An Efficient Algorithm to Extract an Optimal Sub-Circuit by the Minimum Cut
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1301-1308
- Publication Date
- 2001/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
