発見的方法によるグラフの分解

KERNIGHAN B W; LIN S

文献

J-GLOBAL ID：201602016139321694 整理番号：70A0229219

発見的方法によるグラフの分解

An efficient heuristic procedure for partitioning graphs.

出版者サイト複写サービスで全文入手
高度な検索・分析はJDreamⅢで

著者 (2件)： ,
資料名：
巻： 49 号： 2 ページ： 291-307 発行年： 1970年
JST資料番号： B0062A ISSN： 0005-8580 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

節点および枝に重みが付与されているグラフに対し,各部分集合の節点の重みの総和の上限が与えられ,部分集合間を結ぶ枝の重みの総和Tを最小にするように,グラフの節点集合を与えられた数kだけの部分に分割する方法の考察。まず,節点の重みが一様で,k=2の場合についてTを極小にする,すなわち二つの部分集合から1個づつ節,点を選び,交換することにより最もTを減らし得る対を選びこれを繰り返す,方法を提案し,要する手数などを考察する。つぎにこの方法を一般の場合へ適用する方法について言及。プリント配線板の設計に関連;写図3参4

, ,

前のページに戻る