2024-03-29T09:47:59Z
https://nagoya.repo.nii.ac.jp/oai
oai:nagoya.repo.nii.ac.jp:00010824
2023-01-16T03:56:49Z
320:321:322
配線可能性検証のための容量判定グラフとフロー導出グラフ
Two Graphs for Efficient Routability Checking
川口, 泰
磯, 直行
平田, 富夫
open access
Copyright 1997 IEICE
レイアウト設計
概略配線
配線可能性
直接支配集合
VLSIやプリント配線板設計において,配線経路決定を概略配線と詳細配線に分割して行う手法が提案されている.概略配線から詳細配線への変換可能性の検証を行う問題を配線可能性問題という.この検証は配線領域内のカットと呼ばれる線分について,カット上を通過することのできる配線本数(容量)と概略配線でカット上を通過している配線本数(フロー)の比較により行うことができる.主な実行時間は概略配線からフローを求める時間と容量とフローの比較を行う時間である.本論文では効率の良い配線可能性検証のために容量判定グラフの提案を行い,このグラフに含まれる辺についてのみカットとフローの比較を行うことにより配線可能性の検証ができることを示す.また概略配線からフローを求めるためのフロー導出グラフを提案し,このグラフの辺のフローが与えられたならば,容量判定グラフのすべての辺のフローを計算により求めることができることを示す.
電子情報通信学会
1997-01-20
jpn
journal article
VoR
http://hdl.handle.net/2237/12669
https://nagoya.repo.nii.ac.jp/records/10824
http://www.ieice.org/jpn/trans_online/index.html
0913-5707
電子情報通信学会論文誌
J80-A
1
135
142
https://nagoya.repo.nii.ac.jp/record/10824/files/j80-a_1_135.pdf
application/pdf
665.9 kB
2018-02-20