Parallel algorithms for geometric intersection graphs
Sung Kwon Kim, Walter L. Ruzzo · 1990
This dissertation presents efficient parallel algorithms on the PRAM for solving several problems on the interval graphs, circular-arc graphs, and intersection graphs of rectangles, assuming that input graphs are represented by intersection models, instead of standard graph representations such as adjacency matrices and edge lists. Specifically, our results are the following: For interval graphs, we present O(log n) time, n/log n processor algorithms in the EREW PRAM for the problems of computing a depth first search tree, a breadth first search tree, a maximum independent set, a minimum clique cover, a minimum dominating set, and a minimum coloring, assuming that the intervals are initially sorted by x-coordinates. For circular-arc graphs, we give O(log n) time, n/log n processor algorithms in the EREW PRAM for the problems of finding a depth first search tree, a breadth first search tree, a minimum circle cover, a maximum independent set, and a minimum dominating set, assuming the circular-arcs are initially sorted by angles. An O(log$\sp2$n) time, O($n\sp3$/log n) processor algorithm in the CREW PRAM is given for finding a maximum clique. For a set of rectangles, we present O(log n) time, n processor algorithms in the CREW PRAM for the problems of finding a maximum clique and the problems of computing the area and perimeter of the union of rectangles. We also present an O(log n) time, n processor algorithm in the CRCW PRAM for the problem of computing the connected components of the rectangles. Finally, we discuss three geometric problems, namely, region labeling of binary images, finding largest rectangles in a black-and-white grid, and segment-dragging problem, and present efficient parallel solutions for them.