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