層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
スポンサーリンク
概要
- 論文の詳細を見る
k層の制約付きビア数最小化問題(kCVM)とは, k層に割当て可能な初期配線レイアウトが与えられたとき, ビア数が最小となるような配線の層割当てを求める問題である.k=2ならば最適解法が存在し, k=3の場合でも性能のよい発見的解法が得られている.しかし, k≥4のCVMに対する研究は[7]にはあるもののほとんど行われていない.本稿では, k≥3の場合のkCVMの解法を組み合わせて, k≥4なるkCVMを解く発見的解法PNLAを提案し, その性能を実験的に評価する.PNLAの中心的部分は, 所与のネット集合をいくつかの集合に分割し, 各々を2CVM, または3CVMとして解くためのネット集合の分割手法である.
- 社団法人電子情報通信学会の論文
- 2000-01-11
著者
関連論文
- 枝重み付きカクタスに対する発火系列問題の解法
- サイクリックカクタスに対する発火系列問題の解法について
- 次数増加禁止点を持つグラフの指定点3辺連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフの指定点3点連結化問題に対する線形時間アルゴリズム
- 次数増加禁止点を持つグラフに対する点連結度増加問題
- グラフの指定点集合に対する3点連結化問題の解法
- ペトリネットの最小初期マーキング問題に対する発見的解法
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- ペトリネット発火系列問題に対する発見的アルゴリズムFSDTとMAX SAT解法への応用
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN
- ペトリネット発火系列問題の概説
- ペトリネット発火系列問題の概説
- ペトリネットのサイフォン・トラップサポート集合に基づくインバリアント算出法
- CST2000-9 ペトリネットの最小初期マーキング問題に対する発見的アルゴリズムFMDB
- サイクリックカクタスに対する発火系列問題の解法について
- TD-1-11 平面全域部分グラフ抽出法とその応用
- SA-6-1 ペトリネットにおけるサイフォンの抽出法とその応用
- SA-6-8 通信ネットワーク3辺連結化のための分散アルゴリズム
- コンカレント工学研究会の活動を振り返って : 歴代委員長からのメッセージ(一般,コンカレントシステム及び一般)
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- 時間付きペトリネットによるスケジューリングのための発見的アルゴリズムSDS
- A-12-9 Fourier-Motzin法によるペトリネットインバリアントの効率的算法
- CST2000-12 Fourier-Motzkin法によるペトリネットインバリアント計算の効率化
- A-12-6 ペトリネットの発火系列問題の発見的解法について
- CST2000-8 ペトリネット発火系列問題とその関連問題に対する発見的アルゴリズム
- ペトリネットにおけるトークン数下限制約を持つ発火系列問題
- 付加辺の多重度に上限を持つk辺連結化問題に対する発見的解法EAM
- 最大独立点問題解法に基づくTerminal-Vertex Graphにおける全域平面部分グラフ抽出
- D-1-4 通信ネットワークの2辺連結化問題に対する分散アルゴリズムRDBCA
- 非交差道を用いたプリント基板配線領域の見積り手法
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 層割当てのためのネット集合分割に基づく制約付きビア数最小化手法PNLA
- 通信ネットワークの3辺連結化分散アルゴリズム3DECA
- 部分論理回路の縮約に基づくFPGAテクノロジーマッピング法
- Efficient Augmentation to Construct $(\sigma + 1)$-Edge-Connected Simple Graphs (Algorithm Engineering as a New Paradigm)
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- プリント基板設計における非平面接続要求の部品下領域を利用した配線手法
- ペトリネットの発火系列問題に対する新しい発見的解法FSD
- ペトリネットの指定プレース集合を含むサイフォン抽出法
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム
- ペトリネットの発火系列問題に対する新しいヒューリスティックアルゴリズム