Logarithmic Time Parallel Algorithms for Recognizing Comparability and Interval Graphs
Permanent Link(s)
Collections
Author
Novick, Mark B.
Abstract
We give fast parallel algorithms for recognizing ad representing comparability graphs that can be transitively oriented, and interval graphs, the intersection graphs of intervals along the real line. Under the CRCW PRAM model, both algorithms use $O(n^{3})$ processors in $O$(log $n$) time to check if a graph belongs to the desired class, and if it does then a valid representation of the graph can be produced. The algorithms gain their efficiency by using fast algorithms for finding the modular decomposition of a graph. Both problems were known to be in $NC$, but the known algorithms require more time than ours does.
Date Issued
1989-06
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1015
Type
technical report