Finding Group Steiner Trees in Graphs with both Vertex and Edge Weights
Yahui Sun, Xiaokui Xiao, Bin Cui, Saman Halgamuge, Theodoros Lappas, Jun Luo
PROCEEDINGS OF THE VLDB ENDOWMENT | ASSOC COMPUTING MACHINERY | Published : 2021
Given an undirected graph and a number of vertex groups, the group Steiner tree problem is to find a tree such that (i) this tree contains at least one vertex in each vertex group; and (ii) the sum of vertex and edge weights in this tree is minimized. Solving this problem is useful in various scenarios, ranging from social networks to knowledge graphs. Most existing work focuses on solving this problem in vertex-unweighted graphs, and not enough work has been done to solve this problem in graphs with both vertex and edge weights. Here, we develop several algorithms to address this issue. Initially, we extend two algorithms from vertex-unweighted graphs to vertex-and edge-weighted graphs. The..View full abstract
Awarded by Singapore Ministry of Education
We sincerely thank Dr. Bolin Ding  and Dr. Ronghua Li  for sharing codes of their algorithms. This work is sequentially funded by MOE2016-T2-2-022 (2019-2020) from the Singapore Ministry of Education, and a Start Up Grant (SUG) (2020-2021) from the National University of Singapore.