WEKO3
-
RootNode
アイテム
A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs
https://tokushima-u.repo.nii.ac.jp/records/2000468
https://tokushima-u.repo.nii.ac.jp/records/20004685cace86e-15d8-4ffd-aa21-cc00e9331766
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00004258489.pdf (548 KB)
|
|
| Item type | 文献 / Documents(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-03-18 | |||||||||||||||||
| アクセス権 | ||||||||||||||||||
| アクセス権 | open access | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | departmental bulletin paper | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | VoR | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | A Simple Near Optimal Parallel Algorithm for Recognizing Outerplanar Graphs | |||||||||||||||||
| 著者 |
中山, 慎一
× 中山, 慎一
WEKO
1035
× マスヤマ, シゲル
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述 | An outerplanar graph is a graph which can be embedded in the plane so that all vertices lie on the boundary of the exterior face. In this paper, we propose a simple near optimal parallel algorithm for recognizing whether a given graph G is outerplanar in ο(log n) time using ο(nα(l, n)/log n) processors on an arbitrary-CRCW PRAM in the sense that ο(log n)×ο(nα(l, n)/log n)=ο(nα(l, n)) is almost linear with respect to n, where n is the number of vertices in G, α(l, n) is the inverse Ackermann function, which grows extremely slowly with respect to l and n [9] and l=ο(n). Although a near optimal parallel algorithm for general graphs can also be obtained by combining the algorithm in [3] with the algorithm for finding biconnected components [4] [9], our algorithm uses methods completely different from the algorithm in [3]'s, e. g., the well known st-numbering, and is much simpler than [3]'s. | |||||||||||||||||
| 書誌情報 |
en : Journal of mathematics, Tokushima University 巻 30, p. 71-80, 発行日 1997-02-20 |
|||||||||||||||||
| 収録物ID | ||||||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||||||
| 収録物識別子 | 00754293 | |||||||||||||||||
| 収録物ID | ||||||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||||||
| 収録物識別子 | AA00701816 | |||||||||||||||||
| 備考 | ||||||||||||||||||
| 値 | 公開日:2010年1月24日で登録したコンテンツは、国立情報学研究所において電子化したものです。 | |||||||||||||||||
| EID | ||||||||||||||||||
| 識別子 | 63193 | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
