P systems with branch and bound for solving two hard graph problems
-
- Umetsu Kotaro
- Kyushu Institute of Technology
-
- Fujiwara Akihiro
- Kyushu Institute of Technology
説明
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.
収録刊行物
-
- International Journal of Networking and Computing
-
International Journal of Networking and Computing 10 (2), 159-173, 2020
IJNC編集委員会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390285300177196416
-
- NII論文ID
- 130007878671
-
- ISSN
- 21852847
- 21852839
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可