文章基本信息

标题：Asynchronous P systems for hard graph problems
其他标题：Asynchronous P systems for hard graph problems
本地全文：下载
作者：Kohei Tanaka ; Akihiro Fujiwara
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2014
卷号：4
期号：1
页码：2-22
语种：English
出版社：International Journal of Networking and Computing
摘要：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.Â
关键词：membrane computing; asynchronous P system; graph coloring; independent set; vertex cover; clique