Institute of Electrical and Electronics Engineers (IEEE) Acta Medica Okayama 2169-3536 14 2026 A Novel Approximate Solution Method for Euclidean Steiner Tree Problem Based on Genetic Algorithm 122947 122962 EN Liping Zhang Graduate School of Environmental, Life, Natural Science and Technology, Okayama University Tsuyoshi Migita Faculty of Environmental, Life, Natural Science and Technology, Okayama University Norikazu Takahashi Faculty of Environmental, Life, Natural Science and Technology, Okayama University A novel approximate solution method for the Euclidean Steiner tree problem is proposed and its performance is demonstrated through experiments using 195 benchmark problem instances from the OR-Library. Given a finite number of terminal points, the proposed method first generates non-terminal points around each terminal point and at the same location as the Steiner point for each triangle obtained by the Delaunay triangulation for all terminal points. It next runs a genetic algorithm to select a subset of the generated non-terminal points, aiming to minimize the total edge length of a minimum spanning tree for all the terminal points and the selected non-terminal points. It then optimizes the locations of the non-terminal points in the tree using Weiszfeld�fs method, while preserving the topology. It finally refines the tree by adding new non-terminal points, adding and removing edges, and optimizing the locations of all non-terminal points. The experimental results show that, among 150 benchmark problem instances with known optimal solutions, the proposed method successfully constructs a Euclidean Steiner tree for 61 instances. For the remaining 89 instances, it produces an approximate solution whose total edge lengths is less than 100.7% of the optimal. The experimental results also show that the proposed method obtains approximate solutions efficiently: within 1.5 seconds for instances with up to 100 terminal points and within 61 seconds for instances with up to 1,000 terminal points. No potential conflict of interest relevant to this article was reported.

Wiley Acta Medica Okayama 1532-0626 37 27-28 2025 Algebraic Connectivity Maximizing Regular Graphs: Special Case Analysis and Depth�]First Search e70357 EN Masashi Kurahashi Graduate School of Environmental, Life, Natural Science and Technology, Okayama University Najd Salaani Polytech Sorbonne, Sorbonne University Tsuyoshi Migita Faculty of Environmental, Life, Natural Science and Technology, Okayama University Norikazu Takahashi Faculty of Environmental, Life, Natural Science and Technology, Okayama University The algebraic connectivity is an indicator of how well connected a graph is. It also characterizes the convergence speed of some dynamic processes over networks. In this paper, taking into account that homogeneous networks are modeled as regular graphs, we tackle the following problem: given a pair (𝑛, 𝑘) of positive integers such that 𝑘 is less than 𝑛 and kn is an even number, find a 𝑘-regular graph with 𝑛 vertices that have the maximum algebraic connectivity. We first consider some special cases and derive solutions through theoretical analysis. We next present depth-first search algorithms for solving the problem, which reduce the search space by making use of some known properties of the regular graph and the algebraic connectivity.We also show the results of execution of the proposed algorithms for the values of 𝑛 up to 12. No potential conflict of interest relevant to this article was reported.

Springer Science and Business Media LLC Acta Medica Okayama 0925-5001 84 3 2022 A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill�fs global convergence 755 781 EN Takehiro Sano Graduate School of Natural Science and Technology, Okayama University Tsuyoshi Migita Graduate School of Natural Science and Technology, Okayama University Norikazu Takahashi Graduate School of Natural Science and Technology, Okayama University Nonnegative Matrix Factorization (NMF) has attracted a great deal of attention as an effective technique for dimensionality reduction of large-scale nonnegative data. Given a nonnegative matrix, NMF aims to obtain two low-rank nonnegative factor matrices by solving a constrained optimization problem. The Hierarchical Alternating Least Squares (HALS) algorithm is a well-known and widely-used iterative method for solving such optimization problems. However, the original update rule used in the HALS algorithm is not well defined. In this paper, we propose a novel well-defined update rule of the HALS algorithm, and prove its global convergence in the sense of Zangwill. Unlike conventional globally-convergent update rules, the proposed one allows variables to take the value of zero and hence can obtain sparse factor matrices. We also present two stopping conditions that guarantee the finite termination of the HALS algorithm. The practical usefulness of the proposed update rule is shown through experiments using real-world datasets. No potential conflict of interest relevant to this article was reported.

Oxford University Press (OUP) Acta Medica Okayama 2051-1329 10 4 2022 An algorithm for updating betweenness centrality scores of all vertices in a graph upon deletion of a single edge cnac033 EN Yoshiki Satotani Graduate School of Natural Science and Technology, Okayama University , 3-1-1 Tsushima-naka, Kita-ku, Okayama 700-8530, Japan Tsuyoshi Migita Graduate School of Natural Science and Technology, Okayama University , 3-1-1 Tsushima-naka, Kita-ku, Okayama 700-8530, Japan Norikazu Takahashi Graduate School of Natural Science and Technology, Okayama University , 3-1-1 Tsushima-naka, Kita-ku, Okayama 700-8530, Japan Betweenness centrality (BC) is a measure of the importance of a vertex in a graph, which is defined using the number of the shortest paths passing through the vertex. Brandes proposed an efficient algorithm for computing the BC scores of all vertices in a graph, which accumulates pair dependencies while traversing single-source shortest paths. Although this algorithm works well on static graphs, its direct application to dynamic graphs takes a huge amount of computation time because the BC scores must be computed from scratch every time the structure of graph changes. Therefore, various algorithms for updating the BC scores of all vertices have been developed so far. In this article, we propose a novel algorithm for updating the BC scores of all vertices in a graph upon deletion of a single edge. We also show the validity and efficiency of the proposed algorithm through theoretical analysis and experiments using various graphs obtained from synthetic and real networks. No potential conflict of interest relevant to this article was reported.

Acta Medica Okayama 3 2006 A Real-life Test of Face Recognition System for Dialogue Interface Robot in Ubiquitous Environments 1155 1160 EN Fumihiko Sakaue Makoto Kobayashi Tsuyoshi Migita Takeshi Shakunaga Junji Satake <p>This paper discusses a face recognition system for a dialogue interface robot that really works in ubiquitous environments and reports an experimental result of real-life test in a ubiquitous environment. While a central module of the face recognition system is composed of the decomposed eigenface method, the system also includes a special face detection module and the face registration module. Since face recognition should work on images captured by a camera equipped on the interface robot, all the methods are tuned for the interface robot. The face detection and recognition modules accomplish robust face detection and recognition when one of the registered users is talking to the robot. Some interesting results are reported with careful analysis of a sufficient real-life experiment.</p> No potential conflict of interest relevant to this article was reported.