An asynchronous P system with branch and bound for solving Hamiltonian cycle problem (preliminary version)

Abstract

Membrane computing, which is a computational model based on cell
activity, has considerable attention as one of new paradigms of
computations. In the general membrane computing, computationally
hard problems have been solved in a polynomial number of steps using an
exponential number of membranes. However, reduction of the number of
membranes must be considered to make P system more realistic model.

In the paper, we propose an asynchronous P system with branch and
bound, which is a well known optimization technique, to reduce the
number of membranes. The proposed P system solves Hamiltonian cycle
for a graph with n vertices, and works in O(n!) sequential
steps or O(n^2) parallel steps.

In addition, the number of membranes used in the proposed P system
is evaluated using a computational simulation. The experimental
results show validity and efficiency of the proposed P system.