WEKO3
アイテム
平面グラフで最短非交差道を求めるアルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/130268
https://ipsj.ixsq.nii.ac.jp/records/1302688e30b2f4-7b71-4e14-a49e-26d34e892eb2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00001342023.pdf (234.2 kB)
|
|
| Item type | National Convention(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 1996-09-04 | |||||
| タイトル | ||||||
| タイトル | 平面グラフで最短非交差道を求めるアルゴリズム | |||||
| タイトル | ||||||
| 言語 | en | |||||
| タイトル | An algorithm for finding non-crossing paths with shortest distance in plane graph | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||
| 資源タイプ | conference paper | |||||
| 著者所属 | ||||||
| 東北大学大学院情報科学研科 | ||||||
| 著者所属 | ||||||
| 茨城大学工学部 | ||||||
| 著者所属 | ||||||
| 東北大学大学院情報科学研科 | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Graduate School of Information Sciences, Tohoku University | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Faculty of Engineering, Ibaraki University | ||||||
| 著者所属(英) | ||||||
| en | ||||||
| Graduate School of Information Sciences, Tohoku University | ||||||
| 論文抄録 | ||||||
| 内容記述タイプ | Other | |||||
| 内容記述 | 平面に埋め込まれているグラフ,すなわち平面グラフで,指定されたk個の端子対間の互いに点素で長さの総和が最小なk本の道を求める問題はVLSIの一層配線問題等に応用可能である.しかし この問題はNP完全であるので,効率のよいアルゴリズムはありそうにない.ここで,グラフの辺はVLSIの配線領域に対応している.一つの配線領域に複数の配線を通せる配線モデルでは,この一層配線問題は長さの総和が最小な"非交差道"を求める問題に帰着する.ここで,"非交差道"とは点や辺を共有するかもしれないが互いに平面上で交差はしていない道のことである.端子が置かれる面の個数に制約がある場合には非交差道を求める問題が効率よく解けることが期待される.本論文ではk個の端子対が平面グラフGの指定された3つの面の周上にのみ存在する場合に,長さの総和最小なk本の非交差道を求めるO(n log n)時間アルゴリズムを与える.ここでnはGの点数である.また,kは必ずしも定数とは限らない.このアルゴリズムは,例えばVLSI配線の最終段階に現れる,チップの外周におかれたパッドと内部ブロック周囲にあるビンを結ぶ一層配線問題に適用できる.なお,平面グラフの二つの面の周上にのみ端子が存在する場合に長さの総和最小なk本の非交差道を求めるO(n log n)時間のアルゴリズムが知られている. | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AN00349328 | |||||
| 書誌情報 |
全国大会講演論文集 巻 第53回, 号 ソフトウェア科学・工学, p. 355-356, 発行日 1996-09-04 |
|||||
| 出版者 | ||||||
| 言語 | ja | |||||
| 出版者 | 情報処理学会 | |||||
