A heuristic method for solving the Steiner tree problem in graphs using network centralities
PLOS ONE · 2024
DOI: 10.1371/journal.pone.0303764 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS ONE, 2024. Verfasst von Misa Fujita und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Electrical and Electronic Engineering, School of Engineering, Chukyo University, Nagoya-shi, Aichi, Japan. Hauptthemen laut MEDLINE: Algorithms, Heuristics. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Japan Society for Promotion of Science.
Abstract (Originalsprache)
We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Department of Electrical and Electronic Engineering, School of Engineering, Chukyo University, Nagoya-shi, Aichi, Japan.
- Department of Management Science, Graduate School of Engineering, Tokyo University of Science, Katsushika-ku, Tokyo, Japan.
- Graduate School of Science and Engineering, Saitama University, Sakura-ku, Saitama, Japan.
- Department of Electrical, Electronics and Communication Engineering, Faculty of Fundamental Engineering, Nippon Institute of Technology, Miyashiro-cho, Minami-saitama-gun, Saitama, Japan.
- Department of Information and Computer Technology, Faculty of Engineering, Tokyo University of Science, Katsushika-ku, Tokyo, Japan.
ORCID-Profile: Misa Fujita, Yutaka Shimada
Förderung
- Japan Society for Promotion of Science
Zitieren
APA
Fujita, M., Shimada, Y., Kimura, T., & Ikeguchi, T. (2024). A heuristic method for solving the Steiner tree problem in graphs using network centralities. PLOS ONE. https://doi.org/10.1371/journal.pone.0303764
Vancouver
Fujita M, Shimada Y, Kimura T, Ikeguchi T. A heuristic method for solving the Steiner tree problem in graphs using network centralities. PLOS ONE. 2024. doi:10.1371/journal.pone.0303764
BibTeX
@article{Fujita2024,
author = {Fujita, Misa and Shimada, Yutaka and Kimura, Takayuki and Ikeguchi, Tohru},
title = {A heuristic method for solving the Steiner tree problem in graphs using network centralities},
journal = {PLOS ONE},
year = {2024},
doi = {10.1371/journal.pone.0303764}
}
EUVIMED