Faculty Profiles - FUJIWARA Akihiro

Papers - FUJIWARA Akihiro

Division display1 - 20 of about 81／ All the affair displays >>

An asynchronous P system with improved branch and bound for solving the minimum Steiner tree Reviewed International journal

Ueno R., Fujiwara A.

Proceedings 2024 12th International Symposium on Computing and Networking Workshops Candarw 2024 236 - 239 2024.11

An asynchronous P system with branch and bound for the minimum Steiner tree Reviewed International journal

Ueno Reo, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC Editorial Committee ) 14 ( 2 ) 248 - 261 2024.07

Authorship：Last author,　Corresponding author Language：English Publishing type：Research paper (scientific journal)

Membrane computing, also known as a P system, is a computational model inspired by the activity of living cells. P systems work in a polynomial number of steps, and several have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction in the number of membranes must be considered in order to make a P system a more realistic model. In the present paper, we propose an asynchronous P system using branch and bound to solve the minimum Steiner tree problem. The proposed P system solves for the minimum Steiner tree with n vertices and m edges in O(n^2) parallel steps or O(2^mn^2) sequential steps. We evaluate the number of membranes used in the proposed P system through experimental simulations. Our experimental results show the validity and efficiency of the proposed P system.

DOI： 10.15803/ijnc.14.2_248

Kyutacar

CiNii Research

Other Link： https://kyutech.repo.nii.ac.jp/records/2001160

An asynchronous P system for solving the minimum Steiner tree with branch and bound Reviewed

Ueno R., Fujiwara A.

Proceedings - 2023 11th International Symposium on Computing and Networking Workshops, CANDARW 2023 128 - 134 2023.11

An asynchronous P system with the Bron-Kerbosch algorithm for solving the maximum clique Reviewed International journal

Noguchi Takuya, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC Editorial Committee ) 13 ( 2 ) 131 - 148 2023.07

Authorship：Last author,　Corresponding author Language：English Publishing type：Research paper (scientific journal)

Membrane computing, which is also known as a P system, is a computational model inspired by the activity of living cells. Several P systems, which work in a polynomial number of steps, have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction of the number of membranes must be considered in order to make a P system a more realistic model.

In the present paper, we propose asynchronous P systems based on the Bron-Kerbosch algorithm for solving the maximum clique problem with fewer membranes. The proposed P systems solve the maximum clique with n vertices in O(n^2) parallel steps or O(n^2 2^n) sequential steps.

We evaluate the number of membranes used in the proposed P systems by comparing with the numbers of membranes used in known P systems. Our experimental results demonstrate the validity and efficiency of the proposed P systems.

DOI： 10.15803/ijnc.13.2_131

CiNii Research

Robustness proofs for asynchronous P systems Reviewed International journal

Tojima N., Fujiwara A.

10th International Symposium on Applied Engineering and Science (SAES2022) 2022.12

Robust optimization algorithms for multi-objective knapsack problem Reviewed International journal

Miyamoto T., Fujiwara A.

13th International Workshop on Advances in Networking and Computing 2022.11

An asynchronous P system for solving the maximum clique problem with the Bron-Kerbosch algorithm Reviewed International journal

Noguchi T., Fujiwara A.

4th International Workshop on Parallel and Distributed Algorithms and Applications 2022.11

An asynchronous P system with a DPLL algorithm for solving SAT Reviewed International journal

Noguchi Takuya, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC Editorial Committee ) 12 ( 2 ) 238 - 252 2022.07

Authorship：Corresponding author Language：English Publishing type：Research paper (scientific journal)

Membrane computing, which is also known as P system, is a computational model inspired by the activity of living cells. Several efficient P systems, which work in a polynomial number of steps, have been proposed for solving computationally hard problems. However, most of the proposed algorithms use an exponential number of membranes, and reduction of the number of membranes must be considered in order to make the P system a more realistic model.

In the present paper, we propose an asynchronous P system with a Davis-Putnam-Logemann-Loveland (DPLL) algorithm, which is a set of rules for solving a satisfiability problem (SAT) efficiently, in an attempt to reduce the number of membranes. The proposed P system solves SAT with n variables and m clauses in O(mn2) parallel steps or O(mn22n) sequential steps.

We evaluate the number of membranes used in the proposed P system by comparison with the number of membranes used in known P systems. The experimental result demonstrates the validity and efficiency of the proposed P system.

DOI： 10.15803/ijnc.12.2_238

CiNii Research

Robust asynchronous P systems for basic operations Reviewed International journal

N. Tojima, A. Fujiwara

Symposium on Computational Science (CSCI-ISCS) 2021.12

An asynchronous P system with branch and bound for solving the subset sum problem Reviewed International journal

Nagao K., Fujiwara A.

Proceedings - 2021 9th International Symposium on Computing and Networking Workshops, CANDARW 2021 241 - 247 2021.11

An asynchronous P system with a DPLL algorithm for solving a satisfiability problem Reviewed International journal

Noguchi T., Fujiwara A.

Proceedings - 2021 9th International Symposium on Computing and Networking, CANDAR 2021 155 - 161 2021.11

Population protocol for the multi-objective knapsack problem Reviewed International journal

C. Kaneko, A. Fujiwara

International Conference on Scientific Computing (in conjunction with CSCE'21) 2021.07

An asynchronous P system for bitonic sort Reviewed International journal

K. Nagao, A. Fujiwara

International Conference on Foundations of Computer Science (in conjunction with CSCE'21) 2021.07

Robust asynchronous P systems for basic operations Reviewed International journal

Tojima N., Fujiwara A.

Proceedings - 2021 International Conference on Computational Science and Computational Intelligence, CSCI 2021 592 - 597 2021.01

An asynchronous P system using branch and bound for maximum independent set

2020.11

An asynchronous P system for counting sort Reviewed

Nagao K., Fujiwara A.

Proceedings - 2020 8th International Symposium on Computing and Networking Workshops, CANDARW 2020 430 - 434 2020.11

An asynchronous P system with branch and bound for solving the knapsack problem Reviewed

Nakano Y., Fujiwara A.

Proceedings - 2020 8th International Symposium on Computing and Networking Workshops, CANDARW 2020 230 - 236 2020.11

P systems with branch and bound for solving two hard graph problems Reviewed

Umetsu Kotaro, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC Editorial Committee ) 10 ( 2 ) 159 - 173 2020.01

Authorship：Corresponding author Language：English Publishing type：Research paper (scientific journal)

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.

DOI： 10.15803/ijnc.10.2_159

CiNii Article

CiNii Research

Other Link： https://ci.nii.ac.jp/naid/130007878671

Population-based Search Relying on Spatial and/or Temporal Scale-free Behaviors of Individuals Reviewed International journal

2019.12

Strawberry optimization for multi-objective knapsack problem Reviewed

2019.11

　PREV- NEXT 　

<FUJIWARA Akihiro>

Papers - FUJIWARA Akihiro