分割可能バス付きプロセッサアレー上の論理行列積とグラフ問題への応用

前場 隆史  菅谷 光啓  辰巳 昭治  阿部 健一  

誌名
電子情報通信学会論文誌 A   Vol.J82-A   No.3   pp.487-491
発行日: 1999/03/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: レター
専門分野: 
キーワード: 
分割可能バス付きプロセッサアレー,  論理行列積,  グラフ問題,  

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




あらまし: 
分割可能バス付きプロセッサアレー上で論理行列積を O(1) 時間で計算する アルゴリズムを構成し,グラフの推移閉包,無向グラフの連結成分抽出, 有向グラフの弱連結及び強連結成分抽出,非巡回有向グラフのトポロジカル ソーティングを O(log n) 時間で実行できることを述べる.