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. Fast Parallel Algorithms for the Modular Decomposition

Fast Parallel Algorithms for the Modular Decomposition

File(s)
89-1016.ps (500 KB)
89-1016.pdf (886.51 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6816
Collections
Computer Science Technical Reports
Author
Novick, Mark B.
Abstract

A module in a graph is like a black box: all the vertices in the module look the same to vertices not in the module. This paper gives the first $NC$ algorithm for finding the modular decomposition of a graph. The algorithm runs in $O$(log $n$) time using $O(n^{3})$ processors on a CRCW PRAM. This decomposition is used to obtain fast sequential and parallel algorithms for solving graph problems on graphs of bounded module size, e.g. the class of cographs where each module with more than one vertex is either disconnected or its complement is disconnected. These graph problems include minimum coloring, maximum clique, matching, Hamiltonian circuit, and maximum cut. Many of these problems can be solved with $O(n^{3})$ processors in $O$(log $n$) time. All of them can be solved in $NC$. Our modular decomposition algorithm can be used to obtain more efficient algorithms for recognizing and orienting comparability graphs.

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-1016
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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