研究者詳細 - 藤原　暁宏

論文 - 藤原　暁宏

分割表示80 件中 1 - 20 件目／全件表示 >>

An asynchronous P system with branch and bound for the minimum Steiner tree 査読有り国際誌

Ueno Reo, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC編集委員会 ) 14 ( 2 ) 248 - 261 2024年07月

担当区分：最終著者,　責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

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

An asynchronous P system for solving the minimum Steiner tree with branch and bound 査読有り

Ueno R., Fujiwara A.

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

担当区分：最終著者,　責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

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 an asynchronous P system using branch and bound for solving the minimum Steiner tree. The proposed P system solves the minimum Steiner tree with n vertices and m edges in O(n2) parallel steps or O(2mn2) sequential steps.We evaluate the number of membranes used in the proposed P system using experimental simulations. Our experimental results show validity and efficiency of the proposed P system.

DOI： 10.1109/CANDARW60564.2023.00029

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85185722867&origin=inward

An asynchronous P system with the Bron-Kerbosch algorithm for solving the maximum clique 査読有り国際誌

Noguchi Takuya, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC編集委員会 ) 13 ( 2 ) 131 - 148 2023年07月

担当区分：最終著者,　責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

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 査読有り国際誌

Tojima N., Fujiwara A.

10th International Symposium on Applied Engineering and Science (SAES2022) 2022年12月

Robust optimization algorithms for multi-objective knapsack problem 査読有り国際誌

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 査読有り国際誌

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 査読有り国際誌

Noguchi Takuya, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC編集委員会 ) 12 ( 2 ) 238 - 252 2022年07月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

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 査読有り国際誌

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 査読有り国際誌

Nagao K., Fujiwara A.

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

担当区分：最終著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Membrane computing is a computational model inspired by living cell activity. Using the membrane computing, a number of computationally hard problems have been solved by using exponential number of natural materials. However, existing algorithms for computationally hard problems define a huge number of evolution rules to execute arithmetic operations.In the present paper, we propose an asynchronous P system with branch and bound for solving the subset sum problem by applying existing P systems for elementary operations. Experimental results for the proposed P system show that the proposed method contributes to the large reduction of the numbers of evolution rules and membranes.

DOI： 10.1109/CANDARW53999.2021.00047

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85124166215&origin=inward

An asynchronous P system with a DPLL algorithm for solving a satisfiability problem 査読有り国際誌

Noguchi T., Fujiwara A.

Proceedings - 2021 9th International Symposium on Computing and Networking, CANDAR 2021 155 - 161 2021年11月

担当区分：最終著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Membrane computing, which is also known as a 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 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({m}n^{2}) parallel steps or O(mn2^{n}) 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. 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.1109/CANDAR53791.2021.00029

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85124127607&origin=inward

An asynchronous P system for bitonic sort 査読有り国際誌

K. Nagao, A. Fujiwara

International Conference on Foundations of Computer Science (in conjunction with CSCE'21) 2021年07月

Population protocol for the multi-objective knapsack problem 査読有り国際誌

C. Kaneko, A. Fujiwara

International Conference on Scientific Computing (in conjunction with CSCE'21) 2021年07月

Robust asynchronous P systems for basic operations 査読有り国際誌

Tojima N., Fujiwara A.

Proceedings - 2021 International Conference on Computational Science and Computational Intelligence, CSCI 2021 592 - 597 2021年01月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Membrane computing, which is a computational model inspired by living cell activity, has attracted considerable attention as a new computation paradigm. Using membrane computing, several arithmetic operations have been proposed. However, when the cellular activity of an organism is used as computational hardware, the cells may be stopped or vanish for some reason. Therefore, a robust algorithm, which continues calculation even if some of the cells are stopped or vanish, is necessary for membrane computing.In the present paper, we propose robust algorithms for basic operations, which are logic functions and addition, using an asynchronous P system. The proposed P system can obtain a correct solution even if some objects vanish at any stage of computation.

DOI： 10.1109/CSCI54926.2021.00041

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85133905700&origin=inward

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

Y. Nakano, A. Fujiwara

11th International Workshop on Networking, Computing, Systems, and Software 2020年11月

An asynchronous P system for counting sort 査読有り

K. Nagao, A. Fujiwara

11th International Workshop on Advances in Networking and Computing 430 - 434 2020年11月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Membrane computing, which is a computational model based on cell activity, has attracted considerable attention as a new paradigm in computation. Using membrane computing, several algorithms for elementary operations, such as sorting, have been proposed. However, the proposed algorithms for sorting in membrane computing have different types of inputs. In addition, there is room for improvement on the complexities of the proposed algorithms.In the present paper, we propose an asynchronous P system based on counting sort for inputs representing binary numbers. The proposed P system sorts n binary numbers of m bits in O(mn2) sequential steps and O(mn) parallel steps.

DOI： 10.1109/CANDARW51189.2020.00088

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85102200747&origin=inward

An asynchronous P system with branch and bound for solving the knapsack problem 査読有り

Y. Nakano, A. Fujiwara

12th International Workshop on Parallel and Distributed Algorithms and Applications 230 - 236 2020年11月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

Membrane computing, which is a computational model based on cell activity, has considerable attention as a new computation paradigm. In general membrane computing, computationally hard problems have been solved in a polynomial number of steps using an exponential number of membranes. However, 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 an asynchronous P system for the 0/1 knapsack problem using branch and bound, which is a well-known optimization technique. The proposed P system solves the knapsack problem with n items and works in O(n2n) sequential steps or O(n2) parallel steps.In addition, the numbers of membranes used in the proposed P system are evaluated by computational simulation. The experimental results show the validity and efficiency of the proposed P system.

DOI： 10.1109/CANDARW51189.2020.00052

Scopus

その他リンク： https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85102204848&origin=inward

P systems with branch and bound for solving two hard graph problems 査読有り

Umetsu Kotaro, Fujiwara Akihiro

International Journal of Networking and Computing ( IJNC編集委員会 ) 10 ( 2 ) 159 - 173 2020年01月

担当区分：責任著者記述言語：英語掲載種別：研究論文（学術雑誌）

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

その他リンク： https://ci.nii.ac.jp/naid/130007878671

Population-based Search Relying on Spatial and/or Temporal Scale-free Behaviors of Individuals 査読有り国際誌

Z. Zhang, Y. Zhu, A. Fujiwara, K. Ohinishi

The 2019 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2019) 2019年12月