一般のグラフの埋込み面積のMax-Min下界
スポンサーリンク
概要
- 論文の詳細を見る
VLSIの設計においては，面積がどのような大きさになるであろうかという問題は大変興味をひく問題である．そこで，回路の素子および配線を，形式的には無向グラフの頂点および辺と考え，このグラフを一定の埋込みの方式（これを埋込みmodelという）に従って長方形格子グラフ上に埋込むのに十分な面積，あるいは必要となる面積をまず明らかにすることがこの問題を考察するに当たって第1の目標となる．本論文は，頂点を［長辺の長さ］/［短辺の長さ］≦定数であるような長方形グラフに対応させ，辺の像（配線）が長方形の頂点領域の内部を通過することを許さない埋込みmodelの下で，一般のn点d次グラフに対する面積のMax-Min下界がΩ（d2n2）となることを示す．この結果，従来知られている上界O（d2n2）はすべてのn点d次グラフを対象とする限りそれ以上の改善ができないことを明らかにする．
- Institute of Electronics, Information and Communication Engineersの論文
- 1988-10-00
著者
関連論文
- ソート集合のある分割に対する並列アルゴリズムについて
- マルチメディアを用いた導入教育
- 命令再構成型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下界
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当