Edge- and Node-Disjoint Paths in P Systems

Details Edge- and Node-Disjoint Paths in P Systems Edge- and Node-Disjoint Paths in P Systems

2010-11-02

arxiv.org/abs/1011.0495v1

EPTCS 40, 2010, pp. 121-141

Computer Science

Distributed, Parallel, and Cluster Computing

In Proceedings MeCBIC 2010, arXiv:1011.0051

Scientific paper

10.4204/EPTCS.40.9

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.

Affiliated with

Also associated with

No associations

Rating

Edge- and Node-Disjoint Paths in P Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Edge- and Node-Disjoint Paths in P Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edge- and Node-Disjoint Paths in P Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-594441