dc.contributor.author Novick, Mark B. en_US dc.date.accessioned 2007-04-23T17:45:20Z dc.date.available 2007-04-23T17:45:20Z dc.date.issued 1990-02 en_US dc.identifier.citation http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1096 en_US dc.identifier.uri https://hdl.handle.net/1813/6936 dc.description.abstract Intersection graphs have often been used to model special structure in graph problems for both practical and theoretical reasons. Often problems can be solved efficiently for a restricted class of graphs that are provably hard for graphs in general. In this thesis, we examine parallel (i.e. $NC$) algorithms for exploiting the special structure of different types of intersection graphs to solve common graph problems. First, we show how to recognize whether a graph belongs to one of the special families of intersection graphs. Only after this has been done can we take advantage of the properties of a class of intersection graphs. Let $\cal F$ be a family of nonempty sets. Then the intersection graph of $\cal F$ is obtained by representing each set in $\cal F$ by a vertex and connecting two vertices if and only if their corresponding sets have a nonempty intersection. In this dissertation, several types of intersection graphs will be examined, among them interval, comparability, chordal, path, and circle graphs. Interval and comparability graphs arise often when solving scheduling problems. Chordal graphs have applications in solving sparse systems of linear equations and in relational database theory. Each of these classes of intersection graphs is closed under a natural graph composition operation, namely one of modular composition, clique identification, and split composition. In this thesis, we show that the number of intersection representations for a graph in one of these classes depends on how the graph was composed from indecomposable graphs. Also, we show how to efficiently decompose any graph (i.e. perform that inverse of the above composition operations) in parallel. Often if we can solve a problem efficiently on the indecomposable pieces of a graph, then we can solve this same problem efficiently on the graph itself in parallel. Thus we can extend many of our results on special classes of intersection graphs to more general classes of graphs. en_US dc.format.extent 8155873 bytes dc.format.extent 1642777 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 Parallel Algorithms for Intersection Graphs en_US dc.type technical report en_US
﻿