A linear time complexity of breadth-first search using P system with membrane division
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi Publishing Corporation
2013
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/48994/1/SitiMariyamShamsuddin2013_Alineartimecomplexity.pdf |
| _version_ | 1796859417717637120 |
|---|---|
| author | Salehi, Einallah Shamsuddin, Siti Mariyam Nemati, Kourosh |
| author_facet | Salehi, Einallah Shamsuddin, Siti Mariyam Nemati, Kourosh |
| author_sort | Salehi, Einallah |
| collection | ePrints |
| description | 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 O (2 d) to O (d) |
| first_indexed | 2024-03-05T19:26:52Z |
| format | Article |
| id | utm.eprints-48994 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-03-05T19:26:52Z |
| publishDate | 2013 |
| publisher | Hindawi Publishing Corporation |
| record_format | dspace |
| spelling | utm.eprints-489942018-10-14T08:21:50Z http://eprints.utm.my/48994/ A linear time complexity of breadth-first search using P system with membrane division Salehi, Einallah Shamsuddin, Siti Mariyam Nemati, Kourosh QA76 Computer software 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 O (2 d) to O (d) Hindawi Publishing Corporation 2013 Article PeerReviewed application/pdf en http://eprints.utm.my/48994/1/SitiMariyamShamsuddin2013_Alineartimecomplexity.pdf Salehi, Einallah and Shamsuddin, Siti Mariyam and Nemati, Kourosh (2013) A linear time complexity of breadth-first search using P system with membrane division. Mathematical Problems In Engineering, 2013 . ISSN 1024-123X http://dx.doi.org/10.1155/2013/424108 |
| spellingShingle | QA76 Computer software Salehi, Einallah Shamsuddin, Siti Mariyam Nemati, Kourosh A linear time complexity of breadth-first search using P system with membrane division |
| title | A linear time complexity of breadth-first search using P system with membrane division |
| title_full | A linear time complexity of breadth-first search using P system with membrane division |
| title_fullStr | A linear time complexity of breadth-first search using P system with membrane division |
| title_full_unstemmed | A linear time complexity of breadth-first search using P system with membrane division |
| title_short | A linear time complexity of breadth-first search using P system with membrane division |
| title_sort | linear time complexity of breadth first search using p system with membrane division |
| topic | QA76 Computer software |
| url | http://eprints.utm.my/48994/1/SitiMariyamShamsuddin2013_Alineartimecomplexity.pdf |
| work_keys_str_mv | AT salehieinallah alineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision AT shamsuddinsitimariyam alineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision AT nematikourosh alineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision AT salehieinallah lineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision AT shamsuddinsitimariyam lineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision AT nematikourosh lineartimecomplexityofbreadthfirstsearchusingpsystemwithmembranedivision |