Parallel skeletons for divide-and-conquer and branch-and-bound techniques

The article describes the parallel implementation of skeletons for the divide-and-conquer and branch-and-bound techniques. The user has to choose a paradigm and has to specify for it the type of the problem, the type of solution and the specific characteristics of the technique using the C++ programming language. This information is combined with the provided resolution skeleton to obtain a sequential program and a parallel program. The paper describes the parallel implementation of the skeletons using MPI. Computational results on a Linux-cluster of PCs, Cray T3E and Origin 3000 are presented.