N Highest Weight K-Clique Algorithm


  • 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: