Parallel Computation on Interval Graphs: Algorithms and Experiments - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

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.
Fichier principal
Vignette du fichier
RR2000-43.pdf (377.35 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102081 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102081 , version 1

Citer

Afonso Ferreira, Isabelle Guérin-Lassous, Karina Marcus, Andrew Rau-Chaplin. Parallel Computation on Interval Graphs: Algorithms and Experiments. [Research Report] LIP RR-2000-43, Laboratoire de l'informatique du parallélisme. 2000, 2+25p. ⟨hal-02102081⟩
13 Consultations
178 Téléchargements

Partager

Gmail Facebook X LinkedIn More