矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
1つの矩形を内点で交わることのない幾つかの水平および垂直線分によって矩形へと細分した図形を矩形描画(rectangular drawing)あるいはフロアプラン(floorplan)と呼ぶ.n個の矩形を持つフロアプランの個数R(n)を与える簡単な式はまだ得られていないが,漸近的に等比数列として近似できる-定数c=lim_<n→∞>R(n)^<1/n>が存在する-ことが示されている.しかしながら,これまでに知られているcの値の上界と下界はそれぞれ25と11.56であり,その差は大きいものであった.本報告では上界に対する大幅な改良となるc≦13.5を示す.
- 社団法人電子情報通信学会の論文
- 2008-06-20
著者
-
井上 陽平
株式会社ルネサステクノロジ
-
高橋 俊彦
新潟大学教育研究院自然科学系
-
藤巻 亮
新潟大学大学院自然科学研究科
-
高橋 俊彦
新潟大学大学院自然科学研究科
-
高橋 俊彦
新潟大学教育研究院 自然科学系
-
高橋 俊彦
新潟大
関連論文
- RaoのRectilinear Steiner Arborescenceアルゴリズムにおける摂動の効果
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの多項式時間数え上げ (第21回 回路とシステム軽井沢ワークショップ論文集) -- (組合せ的アルゴリズム)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 並べ替え可能な隣接記号を含む2つの文字列の最長共通部分列問題(グラフ,ペトリネット,ニューラルネット及び一般)
- 矩形迷路のパス決定アルゴリズム(グラフ, ペトリ, ニューラルネット及び一般)
- 矩形迷路のパス決定アルゴリズム(グラフ, ペトリ, ニューラルネット及び一般)
- A-1-6 RaoのRectilinear Steiner Arborescenceアルゴリズムにおける摂動の効果II(A-1.回路とシステム,一般セッション)
- Ford-Fulkersonの最大フロー手続きが停止しない最簡かつ最小のネットワーク(グラフ,ペトリネット,ニューラルネット及び一般)
- Ford-Fulkersonの最大フロー手続きが停止しない最簡かつ最小のネットワーク(グラフ,べトリネット,ニューラルネット及び一般)
- A-1-5 Schroder Pathの列挙(A-1.回路とシステム,一般セッション)
- Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について(物理設計,デザインガイア2010-VLSI設計の新しい大地-)
- Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について(物理設計,デザインガイア2010-VLSI設計の新しい大地-)
- Fujimaki-Takahashi Squeeze:制約グラフの線形時間構成 (第20回 回路とシステム軽井沢ワークショップ論文集) -- (レイアウト)
- 部屋の隣接関係を含んだ順列とフロアプランの対応 (フロアプラン)
- 2.5-dimensional FT Squeeze : 矩形描画の積み重ねの順列表現(ポスターセッション,ネットワーク,通信のための信号処理及び一般)
- 2.5-dimensional FT Squeeze : 矩形描画の積み重ねの順列表現(ポスターセッション,ネットワーク,通信のための信号処理及び一般)
- 2.5-dimensional FT Squeeze : 矩形描画の積み重ねの順列表現(ポスターセッション,ネットワーク,通信のための信号処理及び一般)
- A-1-17 An O(n log n)-time algorithm solving square sub-crossbar problem for two-directional orthogonal rays
- Rectilinear Steiner Arborescence問題の厳密解法における枝刈り規則についてII(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Rectilinear Steiner Arborescence問題の厳密解法における枝刈り規則についてII(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Rectilinear Steiner Arborescence問題の厳密解法における枝刈り規則についてII(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 多端子ネット配線の配線長と混雑度の最小化手法(グラフ,ペトリ,ニューラルネット及び一般)
- 多端子ネット配線の配線長と混雑度の最小化手法(グラフ,ペトリ,ニューラルネット及び一般)
- 平面グラフの直線分描画の高さについて
- AS-1-2 Slicing floorplanの列挙(AS-1.組み合わせ最適化の最新動向,シンポジウムセッション)
- A-1-21 レクトリニア多角形パッキングの O-Tree 表現
- 矩形パッキングのための最大重み減少列を求めるアルゴリズム
- A-1-32 矩形分割の(3n-4)-ビット表現(A-1.回路とシステム,一般セッション)
- A Recurrence for the Number of Baxter Permutations via Rectangular Partition (回路とシステム)
- A Recurrence for the Number of Baxter Permutations via Rectangular Partition (システム数理と応用)
- A Recurrence for the Number of Baxter Permutations via Rectangular Partition
- A Recurrence for the Number of Baxter Permutations via Rectangular Partition
- Slicing Floorplan に対する ZDD (Sequence BDD) の構築
- Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について(回路とシステム研究専門委員会推薦論文)(アルゴリズムとデータ構造・計算複雑度)
- 分割面が長方形である直方体分割の表現法
- Baxter Permutationの列挙(一般)