N Highest Weight K-Clique Algorithm
Introduction
-
K-CliqueWeight, along with its variant K-CliqueDynWeight efficiently detects up to the top N highest weight k-cliques in
vertex-weighted graphs. It was tested on general random graphs and graphs designed for protein-ligand docking.
It incorporates a new approximate graph coloring approach, which provides efficient upper bounds to the size and weight
of a k-clique in the branch-and-bound algorithm.
-
The algorithm achieved a significant increase in speed compared to alternative methods, often by several orders of magnitude.
It is integrated into the existing ProBiS-Dock algorithm for molecular docking, which streamlines the process of drug discovery.
Download & Installation
-
To install the latest version of the K-Clique(Dyn)Weight algorithm follow this link.
-
Weighted graphs that were used in the paper for testing the algorithm are available on the links below. Graphs have integer vertex weights.
Each graph's vertices were shuffled 10-times to test the algorithm's performance with different initial vertex orderings.
Therefore, suffixes int1 - int10.
Graph files:
