Edge- and Node-Disjoint Paths in P Systems

Michael J. Dinneen
(University of Auckland)
Yun-Bum Kim
(University of Auckland)
Radu Nicolescu
(University of Auckland)

In this paper, we continue our development of algorithms used for topological network discovery. We present native P system versions of two fundamental problems in graph theory: finding the maximum number of edge- and node-disjoint paths between a source node and target node. We start from the standard depth-first-search maximum flow algorithms, but our approach is totally distributed, when initially no structural information is available and each P system cell has to even learn its immediate neighbors. For the node-disjoint version, our P system rules are designed to enforce node weight capacities (of one), in addition to edge capacities (of one), which are not readily available in the standard network flow algorithms.

In Gabriel Ciobanu and Maciej Koutny: Proceedings Fourth Workshop on Membrane Computing and Biologically Inspired Process Calculi 2010 (MeCBIC 2010), Jena, Germany, 23 August 2010, Electronic Proceedings in Theoretical Computer Science 40, pp. 121–141.
Published: 30th October 2010.

ArXived at: https://dx.doi.org/10.4204/EPTCS.40.9 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org