Fast Distributed BFS Solution for Edge-Disjoint Paths

We propose an improved synchronous distributed message-based breadth-first search (BFS) solution, to identify maximum cardinality sets of edge-disjoint paths, between a source node and a target node in a digraph. Previously, we presented a BFS based algorithm, NW-BFS-Edge (Nicolescu R, Wu H (2011) BFS solution for disjoint paths in P systems. In: Calude C, Kari J, Petre I, Rozenberg G (eds.) Unconventional computation, lecture notes in computer science, vol. 6714. Springer Berlin, pp 164–176), Nicolescu R, Wu H (2012) New solutions for disjoint paths in P systems. Nat Comput 11:637–651, which is a distributed version of the Edmonds-Karp algorithm Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. J ACM 19(2):248–264. Here, we propose a faster solution, Fast-NW-BFS-Edge, which improves NW-BFS-Edge by detecting and discarding “dead” cells in the first search round. On a set of randomly generated single-source directed acyclic graphs (dags), Fast-NW-BFS-Edge is 8.2 % faster than NW-BFS-Edge. This improvement has been inspired and guided by a P system modelling exercise, but is suitable for any distributed implementation.