dc.contributor.author |
Nicolescu, Radu |
en |
dc.contributor.author |
Wu, Huiling |
en |
dc.date.accessioned |
2013-01-06T21:20:57Z |
en |
dc.date.issued |
2012 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-417 (2012) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/19806 |
en |
dc.description.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). |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartof |
CDMTCS Research Report Series |
en |
dc.rights |
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.subject |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.title |
New Solutions for Disjoint Paths in P Systems |
en |
dc.type |
Report |
en |
dc.rights.holder |
The author(s) |
en |
pubs.author-url |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |
pubs.subtype |
Technical Report |
en |
pubs.elements-id |
370873 |
en |
pubs.org-id |
Science |
en |
pubs.org-id |
School of Computer Science |
en |
pubs.record-created-at-source-date |
2013-01-07 |
en |