Parallel Computation on Interval Graphs: Algorithms and Experiments

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02102081
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:13:47 AM
Last modification on : Sunday, April 28, 2019 - 1:23:09 AM

File

RR2000-43.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102081, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

23