A Parallel Implementation for the Negative Cost Girth Problem.

This paper discusses the implementation of a new parallel algorithm for the negative cost girth (NCG) problem. The girth of an unweighted graph (directed or undirected) is defined as the length of the shortest cycle in the graph. We extend the notion of girth to networks with arbitrary weights in the following way: The negative cost girth of a network is the number of edges of the shortest negative cost cycle (i.e., the negative cost cycle with the fewest number of edges). The NCG problem has been well-studied, and there exist several polynomial time algorithms for the same. This problem finds applications in several domains, including constraint-solving, real-time scheduling, and program verification. In this paper, our focus is on a parallel implementation for solving the NCG problem that runs in $$O(\log k \cdot \log n)$$ parallel time using $$O(n^3)$$ processors, where $$n$$ is the number of vertices, and $$k$$ is the NCG. We conduct an empirical analysis for both the parallel implementation, using MPI, and the corresponding sequential NCG implementation. Our experiments indicate that as the number of processors doubles, the total execution time reduces by approximately one-half. [ABSTRACT FROM AUTHOR]