首页 | 本学科首页   官方微博 | 高级检索  
     


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 gamma 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 THgr 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号