WEKO3
アイテム
平面グラフでスタイナー林を求める並列アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/32650
https://ipsj.ixsq.nii.ac.jp/records/32650ac9a7986-e96e-473f-b28e-f9a35f2e43c9
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL89014002.pdf (917.5 kB)
|
Copyright (c) 1990 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1990-03-12 | |||||||
| タイトル | ||||||||
| タイトル | 平面グラフでスタイナー林を求める並列アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Parallel Algorithms for Finding Steiner Forests in Planar Graphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東北大学工学部通信工学科 | ||||||||
| 著者所属 | ||||||||
| 東北大学工学部通信工学科 | ||||||||
| 著者所属 | ||||||||
| 東北大学工学部通信工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Electrical Communications, Faculty of Engineering Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Electrical Communications, Faculty of Engineering Tohoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Electrical Communications, Faculty of Engineering Tohoku University | ||||||||
| 著者名 |
鈴木, 均
× 鈴木, 均
|
|||||||
| 著者名(英) |
Hitoshi, Suzuki
× Hitoshi, Suzuki
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では，平面グラフGと幾つかのネットが与えられたときにスタイナー林を求めるCREW PRAM上の並列アルゴリズムを与える．スタイナー林とはG上の点素な木で，各木が一つのネットの全ての端子を連結するものである．全ての端子がグラフGの外周上にある場合には，O(n^3/log n)台のプロセッサを用いてO(log^2n)時間でスタイナー林を求めることができる．ここでnはグラフの点数である．またこのアルゴリズムから，各ネットの全ての端子が指定された定数個の面の一つの周上にある場合や，全ての端子が二つの面の周上にある場合（二つの周に端子をもつネットがあってもよい）についてのNCアルゴリズムが得られる．更に，平面グラフの指定された二点の間の最大本数の内素な道を求めるNCアルゴリズムも得られる． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Given an unweighted planar graph G together with nets of terminals, our problem is to find a Steiner forest, i.e., vertex-disjoint trees, each of which interconnects all the terminals of a net. This paper presents several NC algorithms to solve the problems in parallel. An algolithm for the case all the terminals are located on the outer boundary of G runs in O(log^2n) time and uses O(n^3/log n) processors on a CREW PRAM, where n is the number of vertices in G. An algorithm for the case all the terminals of each net lie on one of a fixed number of face boundaries runs in a poly-log time using a polynomial number of processors. On the other hand an algolithm for the case all terminals lie on two face boundaries runs in O(log^2n) time using O(n^6/log n) processors. Furthermore we give an NC algorithm for finding a maximum number of internally disjoint paths between two specified vertices in planar graphs. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1990, 号 23(1989-AL-014), p. 1-8, 発行日 1990-03-12 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
