VLSIによる実現に適したグラフ2分割並列アルゴリズム

礒本 和典  若林 真一  小出 哲士  吉田 典可  

誌名
電子情報通信学会論文誌 A   Vol.J78-A   No.6   pp.692-701
発行日: 1995/06/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: アルゴリズムとデータ構造,計算複雑度
キーワード: 
グラフ2分割,  最小カット,  Kernighan-Lin法,  並列アルゴリズム,  VLSI,  

本文: PDF(721.5KB)>>
論文を購入




あらまし: 
グラフ2分割問題は無向グラフG=(VE)の節点集合を,二つの集合間を接続する枝の数が最小となるように2分割する問題である.この問題はVLSI設計では非常に重要な問題である.本論文では,グラフ2分割問題に対する並列アルゴリズムを提案する.提案アルゴリズムはグラフ2分割問題の代表的なヒューリスティックアルゴリズムであるKernighan-Lin法を基にしており,O(|V|)個のプロセッシング素子から構成される1次元アレー上で動作し,VLSIチップによる実現に適している.提案アルゴリズムの1回のパスの時間計算量はO(|V|)である.シミュレーション実験により,その解がKernighan-Lin法と同程度であることを示す.