分割可能バス付きプロセッサアレー上の全点対間最短経路問題

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

誌名
電子情報通信学会論文誌 A   Vol.J85-A   No.3   pp.403-405
発行日: 2002/03/01
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: レター
専門分野: 
キーワード: 
分割可能バス付きプロセッサアレー,  並列アルゴリズム,  全点対間最短経路問題,  最小全域木,  

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




あらまし: 
本論文では,プロセッサ数が n×n のPASb 上で n 要素の最小(最大)値を O(log log n) 時間で求められることを利用し,N 頂点からなる重み付きグラフの全点対間最短経路長及び最小全域木をN×N×(N/log log N)1/2×(N/log log N)1/2-PASb 上において O(log log N log N) 時間で求められることを示す.