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 0 (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. This implies that the number of communication rounds is independent of the problem size. 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.
Parallel computation on interval graphs: algorithms and experiments
"Concurrency and computation, practice and experience", Volume 14, N°11, September 2002
© Wiley. Personal use of this material is permitted. The definitive version of this paper was published in "Concurrency and computation, practice and experience", Volume 14, N°11, September 2002 and is available at : http://dx.doi.org/10.1002/cpe.700
PERMALINK : https://www.eurecom.fr/publication/1045