Parallel Computation on Interval Graphs: Algorithms and Experiments
Résumé
This paper describes efficient coarse-grained parallel algorithms and implementations for a suite of interval graph problems. Included are algorithms requiring only a constant number of communication rounds for connected components, maximum weighted clique, and breadth-first-search and depth-first-search trees, as well as O(log p) communication rounds algorithms for optimization problems such as minimum interval covering, maximum independent set and minimum dominating set, where p is the number of processors in the parallel system. Implementations of these algorithms are evaluated on parallel clusters, using both Fast Ethernet and Myrinet interconnection networks, and on a CRAY T3E parallel multicomputer, with extensive experimental results being presented and analyzed.
Ce papier décrit des algorithmes parallèles à gros grain efficaces et leur implantation pour l'ensemble des problèmes posés par les graphes d'intervalles. Nous présentons des algorithmes ayant un nombre constant de tondes de communication pour les composantes connexes, la clique des poids maximum et les arbres de recherche en profondeur et en largeur. Nous donnons des algorithmes ayant O(log p) (p est le nombre de processeurs dans le système parallèle) rondes de communication pour les problèmes d'optimisation suivant : couverture minimum par intervalles, ensemble indépendant maximum et ensemble dominant minimum. Les implantations de ces algorithmes sont évalués sur des grappes utilisant les réseaux d'interconnexion Fast Ethernet et Myrinet et sur une machine parallèle CRAY T3E. Nous présentons et analysons les résultats expérimentaux obtenus.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|