期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2010
卷号：40
页码：121-141
DOI：10.4204/EPTCS.40.9
出版社：Open Publishing Association
摘要：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.
