Introduction

• MaxCliqueWeight (and its variant MaxCliqueDynWeight) is a new exact algorithm for identifying a maximum weight clique in a weighted undirected graph. The 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.
• A maximum weight clique is a fully connected subgraph of a graph with the highest sum of its vertex-weights.
• We evaluated the 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. We find 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.

Download & Installation

• To install the latest version of the MaxClique(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:
  • Random weighted graphs
  • DIMACS weighted graphs

Please Cite

• Kati Rozman, An Ghysels, Dušanka Janežič and Janez Konc. An exact algorithm to find a maximum weight clique in a weighted undirected graph. In preparation.