# mts: A light framework for parallelizing tree search codes

arXiv: https://arxiv.org/abs/1709.07605 · HTML: https://mlsanity.com/paper/1709.07605/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2017.

## Built on by (most cited first, 1 of 1)

- [Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions](https://mlsanity.com/paper/2403.00860/) (2024)

## Abstract (arXiv)

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.