Kavli Affiliate: Yi Zhou
| First 5 Authors: Xinyu Wu, Yi Zhou, Jin-Kao Hao, Zhang-Hua Fu,
| Summary:
The Steiner tree problem, which asks for a minimum weighted tree spanning a
given set of terminal vertices in a given graph, is a classic problem arising
in numerous practical applications. Many algorithms about this problem emerged
in the past decade, especially presented in the 11th DIMACS Challenge in 2014
and the 3rd PACE Competition in 2018. In this paper, we present a novel
partition-and-merge algorithm for effectively solving this NP-hard problem in
large graphs. The algorithm first breaks the input graph into small fragments
and then gradually builds up the graph in a level-by-level manner. Intuitively,
the method aggregates information that is found by local search at each level
into the final graph. We assess the algorithm on a wide range of benchmark
instances, showing that the algorithm outperforms the winners of DIMACS and
PACE challenges on large instances and competes favorably with them on small or
middle-sized instances.
| Search Query: ArXiv Query: search_query=au:”Yi Zhou”&id_list=&start=0&max_results=3