Rozman Kati, Ghysels An, Janežič Dušanka, Konc Janez
Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška Ulica 8, 6000, Koper, Slovenia.
IBiTech - BioMMedA Group, Ghent University, Corneel Heymanslaan 10, Entrance 36, 9000, Gent, Belgium.
Sci Rep. 2024 Apr 20;14(1):9118. doi: 10.1038/s41598-024-59689-x.
We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.
我们引入了一种新算法MaxCliqueWeight，用于在加权图中识别最大权团，以及其具有动态变化边界的变体MaxCliqueDynWeight。该算法采用了一种高效的分支定界方法，并结合了一种新的加权图着色算法，该算法能有效地确定图中最大加权团的上界权值。我们在节点数高达10000的随机加权图以及用于各种研究领域的标准DIMACS基准图上对我们的算法进行了评估。我们的研究结果表明，与现有算法相比，计算速度有了显著提高，在高密度随机图和DIMACS图的情况下尤为明显，我们新开发的算法比现有替代算法性能高出几个数量级。新开发的算法及其变体可在http://insilab.org/maxcliqueweight上免费提供给更广泛的研究社区，为包括药物发现在内的各种研究领域的变革性应用铺平了道路。
