Efficient parallel recognition of some circular arc graphs,I |
| |
Authors: | Lin Chen |
| |
Affiliation: | (1) Department of Computer and Information Science, Ohio State University, 43210 Columbus, OH, USA |
| |
Abstract: | We present the first efficient parallel algorithms for recognizing some subclasses of circular arc graphs including circular arc graphs and proper interval graphs. These algorithms run in O(log2
n) time withO(n
3) processors on a CRCW PRAM. An intersection representation can also be constructed within the same resource bounds. Furthermore, we propose some new characterizations of circular arc graphs and proper interval graphs.Portions of this paper have appeared in preliminary form in theProceedings of the 1989 IEEE international Symposium on Circuits and Systems 9], theProceedings of the 1989 Workshop on Algorithms and Data Structures 10], and theProceedings of the 1990 Canadian Conference on Computational Geometry 11]. |
| |
Keywords: | Circular arc graphs Interval graphs Consecutive ones property Parallel algorithm PRAM Claw-free graphs |
本文献已被 SpringerLink 等数据库收录! |
|