In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose two asynchronous P systems for two graph coloring problems. We first propose an asynchronous P system that solves the k-coloring for a graph with n nodes, and show that the proposed P system works in O(k~nn~2) sequential steps or O(n~2) parallel steps using O(n~2) kinds of objects. We next 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(n~(n+2)) sequential steps or O(n~2) parallel steps using O(n~2) kinds of objects.
展开▼
