Rectilinear Steiner arborescence問題の厳密解法における枝刈り規則について(回路とシステム研究専門委員会推薦論文)(アルゴリズムとデータ構造・計算複雑度)
スポンサーリンク
概要
- 論文の詳細を見る
平面上に原点を含むn個の点集合Sが与えられたとき,原点を根とし,原点から各点への経路が(L_1距離で)最短となるように水平線分,垂直線分で構成された根付木をRectilinear Steiner arborescence(RSA)と呼ぶ.また,総線分長が最小となるRSAを最小RSA(MRSA)と呼ぶ.Sが第一象限の点のみからなる場合に,MRSAを求める効率的な厳密解法RSA/DPがLeung and Congによって提案された.本論文では,最初にRSA/DPに二つの枝刈り規則を導入し高速化したアルゴリズムRSA/DP++を示す.計算機実験により,n=100程度の場合,RSA/DP++の生成する部分問題数がRSA/DPの約1/200以下になることを確認した.次に,RSA/DP++に更に二つの新しい枝刈り規則を加えたアルゴリズムRSA/DP+++を提案する.同様の計算機実験により,RSA/DP+++の生成部分問題数はRSA/DP++の約10分の1以下となること,及び2時間以内にn=400程度のMRSAを求めることが可能であることを確認した.
- 2013-07-01
著者
関連論文
- RaoのRectilinear Steiner Arborescenceアルゴリズムにおける摂動の効果
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの(4n-3)-ビット表現(グラフ,ペトリネット,ニューラルネット,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 矩形描画あるいはフロアプランの個数に対する漸近的評価(レイアウト,信号処理,LSI,及び一般)
- 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設計の新しい大地-)
- 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-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の列挙(一般)