Portal de Periódicos da CAPES

Asynchronous P systems for hard graph problems

2014; Volume: 4; Issue: 1 Linguagem: Inglês

10.15803/ijnc.4.1_2

2185-2847

Kohei Tanaka, Akihiro Fujiwara,

semigroups and automata theory

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.