Luo Chuan, Guo Shanyu
School of Software, Beihang University, Beijing, China.
PeerJ Comput Sci. 2024 May 17;10:e2013. doi: 10.7717/peerj-cs.2013. eCollection 2024.
In graph theory, the problem of finding minimum vertex separator (MVS) is a classic NP-hard problem, and it plays a key role in a number of important applications in practice. The real-world massive graphs are of very large size, which calls for effective approximate methods, especially heuristic search algorithms. In this article, we present a simple yet effective heuristic search algorithm dubbed HSMVS for solving MVS on real-world massive graphs. Our HSMVS algorithm is developed on the basis of an efficient construction procedure and a simple yet effective vertex-selection heuristic. Experimental results on a large number of real-world massive graphs present that HSMVS is able to find much smaller vertex separators than three effective heuristic search algorithms, indicating the effectiveness of HSMVS. Further empirical analyses confirm the effectiveness of the underlying components in our proposed algorithm.
在图论中，寻找最小顶点分隔符（MVS）的问题是一个经典的NP难问题，并且它在许多重要的实际应用中起着关键作用。现实世界中的大规模图规模非常大，这就需要有效的近似方法，尤其是启发式搜索算法。在本文中，我们提出了一种简单而有效的启发式搜索算法，称为HSMVS，用于在现实世界的大规模图上求解MVS。我们的HSMVS算法是基于一个高效的构建过程和一个简单而有效的顶点选择启发式方法开发的。在大量现实世界大规模图上的实验结果表明，HSMVS能够找到比三种有效的启发式搜索算法小得多的顶点分隔符，这表明了HSMVS的有效性。进一步的实证分析证实了我们提出的算法中底层组件的有效性。
