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

機関リポジトリ Web Site

書誌事項

タイトル別名
  • VLSI モデル ニ オケル dジ シャフルグラフ ノ ウメコミ メンセキ ニ
  • VLSI　モデル　ニオケル　ｄジ　シャフル　グラフ　ノ　ウメコミ　メンセキ　ニツイテ
  • The Embedding Area of d-Way Shuffle Graph on a VLSI Model

この論文をさがす

抄録

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に比例した面積で埋込めることを示す．

収録刊行物

  • 電子通信学会論文誌. D

    電子通信学会論文誌. D J68-D (5), 1011-1018, 1985-05-20

    Institute of Electronics, Information and Communication Engineers

詳細情報 詳細情報について

問題の指摘

ページトップへ