Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Logarithmic Time Parallel Algorithms for Recognizing Comparability and Interval Graphs

Logarithmic Time Parallel Algorithms for Recognizing Comparability and Interval Graphs

File(s)
89-1015.ps (351.28 KB)
89-1015.pdf (577.05 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6815
Collections
Computer Science Technical Reports
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
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-1015
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance