dc.contributor.author Novick, Mark B. en_US dc.date.accessioned 2007-04-23T17:37:01Z dc.date.available 2007-04-23T17:37:01Z dc.date.issued 1989-06 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1015 en_US dc.identifier.uri https://hdl.handle.net/1813/6815 dc.description.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. en_US dc.format.extent 590897 bytes dc.format.extent 359714 bytes dc.format.mimetype application/pdf dc.format.mimetype application/postscript dc.language.iso en_US en_US dc.publisher Cornell University en_US dc.subject computer science en_US dc.subject technical report en_US dc.title Logarithmic Time Parallel Algorithms for Recognizing Comparability and Interval Graphs en_US dc.type technical report en_US
﻿