大規模ICレイアウトに於ける制約グラフ中のPositive Cycle(PC)検出の高速化
スポンサーリンク
概要
- 論文の詳細を見る
ICレイアウトの一次元コンパクション手法において、n個の頂点からなる制約グラフ中のPCの検出は、通常O(n^2 log n)程度の処理時間を必要とする。ここでは、PCを分割しない範囲で制約グラフの分解を繰り返し、得られたサブグラフ毎にPCの検出を行なう手法を提案する。この手法により処理速度は向上し、特に、各サブグラフに含まれる頂点の数が小さく、バックエッジの数がnに比例するなら、PC検出に要する時間はO(n)になる。このことから、本提案手法は大規模ICレイアウトの処理に有効である。
- 一般社団法人情報処理学会の論文
- 1995-09-21
著者
関連論文
- 株式会社東芝(ORを活用する企業(6))
- 最適性とリスクを考慮した企業の意思決定支援技術 : 与信管理と市場品質管理における適用事例(東芝の経営と顧客向け製品・サービスにおけるOR)
- 電子金融工学の可能性 : 金融データマイニングによる自動格付けを例に(ORと金融工学)
- 1-D-4 クレームデータの購入情報を利用した製品寿命分布の推定方法(信頼性(2))
- 大規模ICレイアウトに於ける制約グラフ中のPositive Cycle(PC)検出の高速化
- PCセンサデータマイニングによるHDD故障予兆検出
- BS-2-1 PCヘルスモニタリングによる機器異常診断(BS-2. 高度なM2Mサービスを支えるネットワークおよびシステム技術,シンポジウムセッション)