Summary
International Symposium on Nonlinear Theory and Its Applications
2016
Session Number:A3L-B
Session:
Number:A3L-B-5
A Construction Method for the Steiner Tree Problem Using Betweenness Centrality
Misa Fujita, Takayuki Kimura, Kenya Jin'no,
pp.-
Publication Date:2016/11/27
Online ISSN:2188-5079
Summary:
Given an undirected weighted graph G = (V,E,c) and a set T, where V is the set of nodes, E is the set of edges, c is a cost function, and T is a subset of nodes called terminals, the Steiner tree is a subgraph that connects all of terminals. The Steiner tree problem in graphs is that of finding the minimum weight Steiner tree. In this study, the KMB algorithm, which is an efficient construction method for Steiner tree problems, is enhanced by considering betweenness centrality. The results of numerical simulations indicate that our improved KMB algorithm shows good performances for various types of benchmark Steiner tree problems.