Fast distributed DFS solutions for edge-disjoint paths in digraphs

We present two new synchronous distributed message-based depth-first search (DFS) based algorithms, Algorithms C and D, to compute a maximum cardinality set of edge-disjoint paths, between a source node and a target node in a digraph. We compare these new algorithms with our previous implementation of the classical algorithm, Algorithm A, and our previous improvement, Algorithm B [10]. Empirical results show that, on a set of random digraphs, our algorithms are faster than the classical Algorithm A, by a factor around 40%. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are suitable for any distributed implementation. To achieve the maximum theoretical performance, our P systems specification uses high-level generic rules applied in matrix grammar mode.