Back to Search
Start Over
A heuristic method for solving the Steiner tree problem in graphs using network centralities.
- Source :
-
PLoS ONE . 6/6/2024, Vol. 19 Issue 6, p1-16. 16p. - Publication Year :
- 2024
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *TREE graphs
*HEURISTIC
*STEINER systems
*COMBINATORIAL optimization
Subjects
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 19
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- PLoS ONE
- Publication Type :
- Academic Journal
- Accession number :
- 177722841
- Full Text :
- https://doi.org/10.1371/journal.pone.0303764