An asynchronous P system with the Bron-Kerbosch algorithm for solving the maximum clique

Abstract

Membrane computing, which is also known as a P system, is a computational model inspired by the activity of living cells. Several P systems, which work in a polynomial number of steps, have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction of the number of membranes must be considered in order to make a P system a more realistic model.

In the present paper, we propose asynchronous P systems based on the Bron-Kerbosch algorithm for solving the maximum clique problem with fewer membranes. The proposed P systems solve the maximum clique with n vertices in O(n^2) parallel steps or O(n^2 2^n) sequential steps.

We evaluate the number of membranes used in the proposed P systems by comparing with the numbers of membranes used in known P systems. Our experimental results demonstrate the validity and efficiency of the proposed P systems.