ID  118 
Author 
Nakayama, Shinichi
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 KnowledgeBased 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 arbitraryCRCW 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 stnumbering, 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  19970220

Remark  公開日:2010年1月24日で登録したコンテンツは、国立情報学研究所において電子化したものです。

EDB ID  
FullText File  
language 
eng

departments 
Science and Technology
