ID | 118 |
Author |
Nakayama, Shin-ichi
Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima
Tokushima University Educator and Researcher Directory
KAKEN Search Researchers
Masuyama, Shigeru
Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
|
Content Type |
Departmental Bulletin Paper
|
Description | 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 Title |
Journal of mathematics, Tokushima University
|
ISSN | 00754293
|
NCID | AA00701816
|
Volume | 30
|
Start Page | 71
|
End Page | 80
|
Sort Key | 71
|
Published Date | 1997-02-20
|
Remark | 公開日:2010年1月24日で登録したコンテンツは、国立情報学研究所において電子化したものです。
|
EDB ID | |
FullText File | |
language |
eng
|
departments |
Science and Technology
|