Efficient parallel recognition of some circular arc graphs, II |
| |
Authors: | L Chen |
| |
Affiliation: | (1) Fundamental Research Laboratory, P. O. Box 18345, 90018 Los Angeles, CA, USA |
| |
Abstract: | Based on Tucker's work, we present an accurate proof of the characterization of proper circular arc graphs and obtain the
first efficient parallel algorithm which not only recognizes proper circular arc graphs but also constructs proper circular
arc representations. The algorithm runs inO(log2
n) time withO(n
3) processors on a Common CRCW PRAM. The sequential algorithm can be implemented to run inO(n
2) time and is optimal if the input graph is given as an adjacency matrix, so to speak.
Portions of this paper appear in preliminary form in theProceedings of the 1989Workshop on Algorithms and Data Structures 2], and theProceedings of the 1994International Symposium on Algorithms and Computation 5]. |
| |
Keywords: | Algorithms Proper circular arc graphs Consecutive l's property Graph recognition PRAM Resource requirements |
本文献已被 SpringerLink 等数据库收录! |
|