IEICE Trans - 巡回シフトの面積時間複雑度について

巡回シフトの面積時間複雑度について

瀬谷　和夫丸岡　章木村　正行

誌名
電子情報通信学会論文誌 D Vol.J66-D No.6 pp.730-737
発行日: 1983/06/25
Online ISSN:
DOI:
Print ISSN: 0913-5713
論文種別: 論文
専門分野:
キーワード:

本文: PDF(596.9KB)>>

あらまし:
本論文は，巡回シフト回路を，VLSIチップのモデルである格子平面に最小の面積で埋め込む問題を考察するものである．まず，巡回シフト回路が，ダブルシャフルグラフの配線パターンを持つ循環型の回路で実現できることを示し，この問題を，ダブルシャフルグラフを格子平面に埋め込む問題に帰着する．そして，シャフルエクスチェンジグラフの埋め込みを利用して，N個の頂点からなるダブルシャフルグラフの埋め込み面積について，O（N²/log^1/2N），O（N²/logN），及びO（N²/log²N）の3つの結果を与える．この最後の結果を用いると，巡回シフトの面積時間複雑度が，最小2分割の考え方を使うことによりΘ（N²log²N）となることも示される．