直近一年間の累計
アクセス数 : ?
ダウンロード数 : ?
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
部局
理工学系