EURO-PAR 1998, 4th International Conference on Parallel Processing, 1-4 September 1998, Southampton, UK / Lecture Notes in Computer Science, Vol 1470/1998
The use of PC clusters interconnected by high performance local networks is one of the major current trends in parallel/distributed computing. We give coarse-grained, BSP-like, 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 PC cluster.
Type:
Conference
City:
Southampton
Date:
1998-09-01
Department:
Digital Security
Eurecom Ref:
1055
Copyright:
© Springer. Personal use of this material is permitted. The definitive version of this paper was published in EURO-PAR 1998, 4th International Conference on Parallel Processing, 1-4 September 1998, Southampton, UK / Lecture Notes in Computer Science, Vol 1470/1998 and is available at : http://dx.doi.org/10.1007/BFb0057943
