ID | 118 |
著者 |
中山, 慎一
Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima
徳島大学 教育研究者総覧
KAKEN研究者をさがす
マスヤマ, シゲル
Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
|
資料タイプ |
紀要論文
|
抄録 | 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.
|
掲載誌名 |
Journal of mathematics, Tokushima University
|
ISSN | 00754293
|
cat書誌ID | AA00701816
|
巻 | 30
|
開始ページ | 71
|
終了ページ | 80
|
並び順 | 71
|
発行日 | 1997-02-20
|
備考 | 公開日:2010年1月24日で登録したコンテンツは、国立情報学研究所において電子化したものです。
|
EDB ID | |
フルテキストファイル | |
言語 |
eng
|
部局 |
理工学系
|