Journal article

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

Abstract

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

University of Melbourne Researchers

Grants

Awarded by Singapore Ministry of Education


Funding Acknowledgements

We sincerely thank Dr. Bolin Ding [14] and Dr. Ronghua Li [31] 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.