最小カットを用いて適切な部分回路を抽出するための効率的手法

• Item type: SIG Technical Reports(1)
• 公開日: 2000-01-12
• タイトル: 最小カットを用いて適切な部分回路を抽出するための効率的手法
• タイトル / 言語: en
• タイトル: An Efficient Algorithm to Extract An Optimal Sub - Circuit by the Minimum Cut
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学工学部電気・電子工学科
• 著者所属: 東京工業大学工学部電気・電子工学科
• 著者所属: 東京工業大学工学部電気・電子工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Inst. of Tech.
• 著者名: 畔上, 謙吾; 高橋, 篤司; 梶谷, 洋司
• 著者名(英): Kengo, Azegami; Atsushi, Takahashi; Yoji, Kajitani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ハイパーグラフからミンカットグラフを生成する手法について述べる。ミンカットグラフは，その有向カットがハイパーグラフのミンカットに1:1で対応する。従来はこのグラフを高速に得るため、その正確さを犠牲にしてきた。本手法は正確さと高速性を同時に達成している。得られたミンカットグラフの有向カット数はその点数に対し指数オーダだが、実際はその点数が小さいため、全探索により実用的な時間内に適切な有向カットを求められることを実験的に示した。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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, we propose an algorithm which gives an exact one without substantial computation overhead. An exhaustive algorithm is proposed to find an optimal sub-circuit that is cut by a min-cut from the rest. By experiments with the industrial data, the proposing method showed a performance enough for practical use.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2000, 号 2(1999-SLDM-094), p. 49-56, 発行日 2000-01-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会