Premium
Parallel computation on interval graphs: algorithms and experiments
Author(s) -
Ferreira A.,
Guérin Lassous I.,
Marcus K.,
RauChaplin A.
Publication year - 2002
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.700
Subject(s) - computer science , myrinet , clique , parallel computing , interval (graph theory) , algorithm , parallel algorithm , interval graph , interconnection , computation , graph , implementation , theoretical computer science , mathematics , chordal graph , message passing , combinatorics , computer network , 1 planar graph , programming language
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. 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. Copyright © 2002 John Wiley & Sons, Ltd.