Skip to Main content Skip to Navigation

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 :
Complete list of metadata
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:13:47 AM
Last modification on : Friday, October 22, 2021 - 4:36:02 PM


Files produced by the author(s)


  • HAL Id : hal-02102081, version 1



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⟩



Les métriques sont temporairement indisponibles