Optimized versions of a distributed algorithm for solving path problems
by
Robert Manger
Department of Mathematics, University of Zagreb, Croatia
Coauthors: Goranka Nogo

Path problems are a family of optimization and enumeration problems that reduce to generation or comparison of paths in graphs. Some well known examples are: checking path existence, finding shortest or most reliable paths, listing all paths, etc. In our previous work we have already proposed a distributed algorithm for solving path problems. In this paper we present three optimized versions of the same algorithm. 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 the PVM package and evaluated on randomly generated problem instances.

Date received: March 4, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadz-24.