Parallel Computation on Interval Graphs using PC Clusters: Algorithms and Experiments. 

A. Ferreira, I. Guerin Lassous, K. Marcus, and A. RauChaplin 

Abstract: The use of PC clusters interconnected by high performance local networks is one of the major current trends in parallel/distributed computing. These clusters can yield effective parallel systems for a fraction of the price of machines using special purpose hardware. Although significant effort has been undertaken on systemlevel and programming environment issues for such clusters, much less attention has been paid to some of the algorithmic issues. In this paper we show that theoretical (BSPlike) coarsegrained models are well adapted to solve important classes of problems on PC clusters. We give coarsegrained parallel algorithms to solve many problems arising in the context of interval graphs, namely connected components, maximum weighted clique, BFS and DFS trees, minimum interval covering, maximum independent set and minimum dominating set. All of the described $p$processor parallel algorithms require only constant or $O(\log p)$ number of communication rounds and are efficient in practice as demonstrated by our experimental results obtained on a Fast Ethernet based cluster. In an interesting interplay between theory and practice we note that superlinear speedups occurred for large data because of swapping factors. 

paper.pdf 
paper.ps 

