An exact algorithm to find a maximum weight clique in a weighted undirected graph.

Area of Science:

• Graph Theory
• Computational Complexity
• Bioinformatics

Background:

• The maximum weight clique problem is crucial in various fields, including computational biology and network analysis.
• Existing algorithms struggle with computational efficiency on large and dense graphs.

Purpose of the Study:

• Introduce MaxCliqueWeight, a novel algorithm for the maximum weight clique problem.
• Enhance computational speed and efficiency for identifying cliques in weighted graphs.
• Provide a freely available tool for the research community.

Main Methods:

• Developed an efficient branch-and-bound approach.
• Integrated a novel weighted graph coloring algorithm for determining upper weight bounds.
• Evaluated performance on random and DIMACS benchmark graphs up to 10,000 nodes.

Main Results:

• MaxCliqueWeight demonstrates significant improvements in computational speed compared to existing algorithms.
• Outperforms alternatives by several orders of magnitude on high-density random and DIMACS graphs.
• The algorithm's efficiency is particularly notable for large-scale graph analysis.

Conclusions:

• MaxCliqueWeight offers a substantial advancement in solving the maximum weight clique problem.
• The algorithm's speed and efficiency facilitate applications in areas like drug discovery.
• The open availability of MaxCliqueWeight and its variant promotes wider research adoption and innovation.