
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An Efficient Algorithm to Extract an Optimal SubCircuit by the Minimum Cut
Kengo R. AZEGAMI Atsushi TAKAHASHI Yoji KAJITANI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E84A
No.5
pp.13011308 Publication Date: 2001/05/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: PAPER Category: VLSI Design Technology and CAD Keyword: circuit partition, hypergraph partition, network flow, mincut, integrated circuit design,
Full Text: PDF(506.1KB)>>
Summary:
We improve the algorithm to obtain the mincut graph of a hypergraph and show an application to the subnetwork extraction problem. The mincut graph is a directed acyclic graph whose directed cuts correspond onetoone to the mincuts of the hypergraph. While the known approach trades the exactness of the mincut graph for some speed improvement, our proposed algorithm gives an exact one without substantial computation overhead. By using the exact mincut graph, an exhaustive algorithm finds an optimal subcircuit that is extracted by a mincut from the circuit. By experiments with the industrial data, the proposing method showed a performance enough for practical use.

