文章基本信息

标题：P systems with branch and bound for solving two hard graph problems
本地全文：下载
作者：Kotaro Umetsu ; Akihiro Fujiwara
期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2020
卷号：10
期号：2
页码：159-173
出版社：International Journal of Networking and Computing
其他摘要：Membrane computing is a computational model based on activity of cells. Using the membrane computing, a number of computationally hard problems have been solved in a polynomial number of steps using an exponential number of membranes. However, the number of membranes denotes the number of cells from practical point of view, and the reduction of the number of membranes must be considered for using the membrane computing in real world. In this paper, we propose asynchronous P systems with branch and bound for reducing the number of membranes for two computationally hard graph problems. We first propose an asynchronous P system that solves Hamiltonian cycle problem for a graph with n vertices, and show that the proposed P system works in O(n^2) parallel steps. We next propose an asynchronous P system that solves the minimum graph coloring for a graph with n vertices, and also show that the P system works in O(n^2) parallel steps. In addition, we evaluate validity of the proposed P systems using computational simulations. The experimental results show the validity and efficiency of the proposed P systems with branch and bound.