Optimized versions of a distributed algorithm for solving path problems

Path problems are a family of optimization and enumeration problems that reduce to generation or comparison of paths in graphs. In this paper we present three optimized versions of a distributed algorithm for solving path problems. The new versions are faster than the original algorithm, but they are applicable only to certain instances of problems, i.e. to undirected, acyclic, and sparse graphs, respectively. We report on experiments, where the three versions have been implemented with PVM and evaluated on randomly generated problem instances.