Solving the Graph Problem on the Maximal Clique Problem on the P-Systems with Mitochondria Enzymes Layer
Source abstract
Abstract
P systems with mitochondria enzymes layer computing is a recent version of P systems; it integrates a new feature inspired from the enzymes gate of a natural cell to the cell-like P systems. The model of a computational layer is well known as a problem of Non-Deterministic (NP-complete) in polynomial time. In this paper, we propose a P systems with enzymes to solve one of the most NP-hard problems, which is the determination of the maximal clique in a given undirected graph. In this context, the evolution strategy proposed is based on using objects under the control of enzymes placed on layers.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: DNA and Biological Computing · Advanced biosensing and bioanalysis techniques · Modular Robots and Swarm Intelligence
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Computer Science Department, BINUS Graduate Program-Doctor of Computer Science, Bina Nusantara University, Jakarta 11480, Indonesia
Graduate School of Industrial Technology, Advanced Institute of Industrial Technology, Tokyo 140-0011, Japan
References (15)
Show source-provided references
1. P systems with proteins on membranes
2. Păun, G. (2002). Introduction to Membrane Computing, Springer.10.1007/978-3-642-56196-2 ↗
3. Păun, G. (2004, January 15–17). Membrane Systems: A Quick Introduction. Proceedings of the 1st International Workshop Unconventional Programming Paradigms—UPP 2004, Le Mont Saint Michel, France.
4. Cardelli, L. (2005). Brane calculi-interactions of biological membranes. Computational Methods in Systems Biology, Springer.10.1007/978-3-540-25974-9_24 ↗
5. Păun, A., and Popa, B. (2006). P Systems with Proteins on Membranes and Membrane Division, Springer.10.1007/11779148_27 ↗
6. P systems with proteins on membranes characterize PSPACE10.1016/j.tcs.2013.03.009 ↗
7. On the Power of Computing with Proteins on Membranes
8. de Leone, R., Murli, A., Pardalos, P.M., and Toraldo, G. (1998). An Exact Parallel Algorithm for the Maximum Clique Problem. High Performance Algorithms and Software in Nonlinear Optimization, Kluwer Academic Publishers.10.1007/978-1-4613-3279-4 ↗
9. A simple and efficient algorithm for the maximum clique finding reusing a heuristic vertex colouring
10. An improved branch and bound algorithm for the maximum clique problem
11. Dynamic Local Search for the Maximum Clique Problem10.1613/jair.1815 ↗
12. Shinano, Y., Fujie, T., Ikebe, Y., and Hirabayashi, R. (April, January 30). Solving the Maximum Clique Problem Using PUBB. Proceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, Orlando, FL, USA.
13. DNA Solution of the Maximal Clique Problem10.1126/science.278.5337.446 ↗
14. Păun, G. (2004, January 15–17). Bio-inspired Computing Paradigms. Proceedings of the 2004 International Conference on Unconventional Programming Paradigms, Le Mont Saint Michel, France.
15. The power of communication: P systems with symport/antiport10.1007/BF03037362 ↗