论文标题
用于在大图中解决施泰纳树问题的分区和合并算法
A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
论文作者
论文摘要
Steiner树问题旨在确定一棵最小的边缘加权树，该树从给定的图中跨越给定的终端顶点。在过去的十年中，已经开发了相当多的算法来解决这个计算挑战性的问题。但是，现有算法通常会遇到求解大实例的困难，即具有大量顶点和终端的图形。在本文中，我们提出了一种新颖的分区和合并算法，以在大图中有效解决此问题。该算法将输入网络分解为小子图，然后以自下而上的方式合并子图。在合并过程中，还通过有效的局部优化创建和优化了子图中的部分施泰纳树。当合并过程结束时，该算法将终止并报告输入图的最终解决方案。我们在广泛的基准实例上评估了算法，表明该算法在大型实例上的表现优于最著名的算法，并在中小型实例上与它们竞争。
The Steiner tree problem aims to determine a minimum edge-weighted tree that spans a given set of terminal vertices from a given graph. In the past decade, a considerable number of algorithms have been developed to solve this computationally challenging problem. However, existing algorithms typically encounter difficulties for solving large instances, i.e., graphs with a high number of vertices and terminals. In this paper, we present a novel partition-and-merge algorithm to effectively solve this problem in large graphs. The algorithm breaks the input network into small subgraphs and then merges the subgraphs in a bottom-up manner. In the merging procedure, partial Steiner trees in the subgraphs are also created and optimized by efficient local optimization. When the merging procedure ends, the algorithm terminates and reports the final solution for the input graph. We evaluated the algorithm on a wide range of benchmark instances, showing that the algorithm outperforms the best-known algorithms on large instances and competes favorably with them on small or medium-sized instances.
