EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A heuristic method for solving the Steiner tree problem in graphs using network centralities

Misa Fujita iD, Yutaka Shimada iD, Takayuki Kimura, Tohru Ikeguchi

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsHeuristicsModels, Theoretical

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}
}
Kostenlos starten →