Abstract:
We propose faster algorithms to identify maximum cardinality sets of edge- and node-disjoint paths, between a source cell and a target cell in P systems. Previously, Dinneen et al. presented two algorithms, based on classical depth- rst search (DFS), which run in O(md) P steps; where m is the number of edges and d is the outdegree of the source node. Combining Cidon's distributed DFS and our new result, Theorem 6, we propose two improved DFS-based algorithms, which run in O(nd) P steps; where n is the number of nodes. We also propose two improved algorithms, based on breadth- rst search (BFS), with O(nf) runtime complexity, where f is the number of disjoint paths. All our algorithms are xed- size, i.e. the number of P rules does not depend on the number of cells in the underlying P system. Empirically, for randomly generated digraphs of various sizes, our DFS-based edge-disjoint algorithm is 39% faster than Dinneen et al.'s edge-disjoint algorithm and our BFS-based edge-disjoint algorithm is 80% faster, in terms of P steps. Our improvements can be considered for any distributed DFS implementation (i.e. not only for P systems).