Show simple item record

dc.contributor.authorNovick, Mark B.en_US
dc.date.accessioned2007-04-23T17:37:01Z
dc.date.available2007-04-23T17:37:01Z
dc.date.issued1989-06en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1015en_US
dc.identifier.urihttps://hdl.handle.net/1813/6815
dc.description.abstractWe 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.en_US
dc.format.extent590897 bytes
dc.format.extent359714 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleLogarithmic Time Parallel Algorithms for Recognizing Comparability and Interval Graphsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics