A Linear Time Complexity of Breadth-First Search Using P System with Membrane Division

Einallah Salehi, Siti Mariyam Shamsuddin and Kourosh Nemati

Mathematical Problems in Engineering, 2013, vol. 2013, 1-11

Abstract:

One of the known methods for solving the problems with exponential time complexity such as NP-complete problems is using the brute force algorithms. Recently, a new parallel computational framework called Membrane Computing is introduced which can be applied in brute force algorithms. The usual way to find a solution for the problems with exponential time complexity with Membrane Computing techniques is by P System with active membrane using division rule. It makes an exponential workspace and solves the problems with exponential complexity in a polynomial (even linear) time. On the other hand, searching is currently one of the most used methods for finding solution for problems in real life, that the blind search algorithms are accurate, but their time complexity is exponential such as breadth-first search (BFS) algorithm. In this paper, we proposed a new approach for implementation of BFS by using P system with division rule technique for first time. The theorem shows time complexity of BSF in this framework on randomly binary trees reduced from to .

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2013/424108.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2013/424108.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:424108

DOI: 10.1155/2013/424108

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().