Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:

• Every subgraph must be a complete graph/clique

• No vertex can be part of two or more subgraphs

• Subgraphs that can be merged with other subgraphs while remaining complete cannot exist

• When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight

Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.

Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.

My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...

Edit: This is my current implementation

• Detect maximal cliques in the graph.

• Sort the cliques in descending order based on their minimum edge weight within the clique.

• Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.

-
After iteration see if any vertices in the original graph are present in any of the selected cliques.

• If all vertices are present, exit.

• If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.

This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.

Edit 2: To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, th

Thus I'm still curious if there are other more efficient approaches to solving the problem.

If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem. Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$.

The problem is para-NP-hard in the unweighted case and the problem is just hard no matter what you do.

There is an algorithm computing the chromatic number in time $O^*(2^n)$ using exponential space, and in time $O(2.2461^n)$ using polynomial space.

The fastest algorithm I know to get the coloring runs in time $O^*((1+\sqrt[3] 3)^n) = O(2.4423^n)$.

[1] Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. An EATCS Series — Texts in Theoretical Computer Science. Springer.

StackExchange Computer Science Q#41946, answer score: 6