Asynchronous P systems for hard graph problems

Abstract

In the present paper, we consider fully asynchronous parallelism in membrane computing and propose asynchronous P systems for the following four graph problems: minimum coloring, maximum independent set, minimum vertex cover, and maximum clique. We first propose an asynchronous P system that solves the minimum graph coloring for a graph with n nodes and show that the proposed P system works in O(nn+2) sequential steps or O(n2) parallel steps by using O(n2) kinds of objects. Second, we propose an asynchronous P system that solves the maximum independent set for a graph with n nodes and show that the proposed P system works in O(n2 · 2n) sequential steps or O(n2) parallel steps by using O(n2) kinds of objects. We next propose two asynchronous P systems that solve the minimum vertex cover and the maximum clique for the same input graph by reduction to the maximum independent set and show that the proposed P system works in O(n2 · 2n) sequential steps or O(n2) parallel steps by using O(n2) kinds of objects.