一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
スポンサーリンク
概要
- 論文の詳細を見る
VLSIの設計において回路の素子および配線を形式的には無向グラフの頂点および辺と考え，これを一定の埋込み方式に従ってVLSIチップを表す格子平面グラフ上に埋め込むのに十分な面積あるいは必要となる面積について考察する．従来，素子に対応する頂点領域の内部に配線することを禁止する埋込みについて議論がなされていたが，本論文ではこれを許す埋込みについて考察する．この埋込み方式で埋込みを行う際に，頂点領域の縦と横の幅をそれぞれグラフの最大次数に比例する大きさ以上にとるとき，頂点数がn，最大次数がdであるグラフの中には，埋込み面積がn2d2に比例するようなものが存在することを示す．また頂点領域の形状に関する制限条件を，例えば，縦幅については設けず横幅についてのみdに比例する大きさ以上にとるといったようにある程度緩めるならば，n2dに比例する埋込み面積を必要とするグラフが存在し，同時に，この制限条件に抵触しない一定の頂点領域形状のもとで，任意のグラフをたかだかn2dに比例する面積で埋め込むことが実際に可能であることを示す．
- Institute of Electronics, Information and Communication Engineersの論文
- 1989-06-20
著者
関連論文
- ソート集合のある分割に対する並列アルゴリズムについて
- マルチメディアを用いた導入教育
- 命令再構成型VLIWプロセッサV++における2つの再構成機能の評価
- バリア同期のためのタスクスケジューリングアルゴリズムとその性能評価
- 命令再構成型VLIWプロセッサV++における適応型再構成戦略
- 重複可能なバリア型同期のための最適バリアスケジューリング
- 概念制約式を用いたプログラミングを可能にするコンパイル手法
- バリアを唯一の同期手段とした場合のタスクスケジューリング
- 自己組織系集団による通信の進化の試み
- ランギーII:仮想的生物による通信の進化
- 複数種の生物集団の共存する人工生命環境の設計
- 概念制約式を用いたプログラミングとプログラム合成
- 星状多角形内の同期式自律分散ロボットの一点集合問題
- 2連結グラフに対するATM網に適した最適な耐故障性ルーティング
- 点集合の強凸-包含を求めるアルゴリズム
- スーパーキューブの耐故障性について
- 2辺連結グラフの4分割について
- グラフのあるk-分割問題に対する効率的なアルゴリズムについて
- 重みつきグラフのk分割問題について
- 3個の空位をもつN×M-平面自動倉庫(N,M≧3)の最小歩数関数
- 異なる半径の数を限定した円集合の凸包を求める最適並列アルゴリズム
- 誤差耐性のある強凸包構成問題に対する並列解法
- 拡張超立方体グラフに対する耐故障性路線割当と直径罹障度
- 円集合の凸包を求める効率の良い並列アルゴリズム
- コンパイラ教育支援システムにおける属性文法に基づく意味解析系提示ツールの作成
- アルゴリズムの可視化に基づくコンパイラ教育支援システム
- k-辺連結有向(無向)グラフに対する高信頼性路線割当の存在条件と計算量
- 通信網に対する高信頼性最適路線割当ての存在条件と計算量の改善
- 3個の空位を持つN×M-平面自動倉庫の最小歩数関数
- 連結グラフの(L,κ)-辺分割線形時間アルゴリズムとκ-辺連結グラフに対する高信頼性路線割当
- 3連結グラフにおける3-独立木構成アルゴリズムと2点間の内点独立路を求めるアルゴリズム
- 非阻塞グラフに関する一考察
- 故障発生時の連結性判定問題を解く分散アルゴリズムについて
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当
- 多重サイクルグラフ上の高信頼性路線割当の構成
- 故障耐性の高い路線割当をもつ通信網の構成問題
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 有向,無効グラフに対する最適なt-spannerの構成について
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 一般のグラフの埋込み面積のMax-Min下界
- 多重サイクルグラフ上の高信頼性路線割当ての構成
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 故障が存在する計算機網に対する連結性判定分散アルゴリズム
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 一般のグラフの埋込み面積のMax-Min下界
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当