  We describe mts, a generic framework for parallelizing certain types of tree
search programs including reverse search, backtracking, branch and bound and
satisfiability testing. It abstracts and generalizes the ideas used in
parallelizing lrs, a reverse search code for vertex enumeration. mts supports
sharing information between processes which is important for applications such
as satisfiability testing and branch-and-bound. No parallelization is
implemented in the legacy single processor programs minimizing the changes
needed and simplying debugging. mts is written in C, uses MPI for
parallelization and can be used on a network of computers. We give four
examples of reverse search codes parallelized by using mts: topological sorts,
spanning trees, triangulations and Galton-Watson trees. We also give a
parallelization of two codes for satisfiability testing. We give experimental
results comparing the parallel codes with other codes for the same problems.
