The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -