VLSIモデルにおけるd次シャフルグラフの埋込み面積について

概要

論文の詳細を見る
VLSIチップを平面格子と呼ばれるグラフでモデル化し，回路を素子間の配線の仕方を表すグラフGで表し，Gを平面格子に埋込んだとき，どれほどの面積を占めるかはVLSIチップの設計においては重要な問題であり，種々のグラフに対して，平面格子に埋込んだときの面積の上下界が議論されている．本論文では，次数が5以上のグラフが埋込めるように拡張したモデルのもとで，d次シャフルグラフを平面格子に埋込む問題を考える．d次シャフルグラフはシャフルエクスチェンジグラフやCCCなどと同様にデータの置換などを高速に行なうことができ理論的にも興味深いグラフである．ここでは，グラフの交差数と面積の関係を用いて，無限個のd，kに対して，dk頂点d次シャフルグラフを埋込むために（dk＋1/k）2に比例した面積が必要となることを示す．この結果を用いると従来の面積の下界が改善される．また，あるグラフGの埋込みに対して，すでに埋込み面積がわかっているグラフを利用したGの埋込みの手法を与え，この結果を用いて，dが2のベキ乗の場合，dk頂点d次シャフルグラフは（dk＋1/k）2に比例した面積で埋込めることを示す．
Institute of Electronics, Information and Communication Engineersの論文
1985-05-20

著者

和田幸一
名古屋工業大学電気情報工学科

VLSIモデルにおけるd次シャフルグラフの埋込み面積について

スポンサーリンク

概要

著者

関連論文

スポンサーリンク