A graph $G$ has nodes $V$ and edges $E$. Let's say I have found the maximum clique or all the cliques in $G$ with any algorithm, such as the Bron-Kerbosch algorithm. After a while, $E$ has been updated to $E'$ by adding new edges to the graph, while $V$ remains the same. I want to find all the cliques again in $G$ with $E'$. Is there a way to use the cliques found earlier and update them in some way instead of finding the cliques from scratch again?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If the goal is to find all cliques, then we start with the fact that every clique in $E$ is also a clique in $E^\prime.$ For each new edge $(a,b),$ look at every pair of cliques $C,\hat{C}$ such that $a\in C$ and $b\in \hat{C}$ and test whether the set of new edges makes $C \cup \hat{C}$ a clique.
If the goal is to find a maximum clique, do the above and update the maximum clique whenever a new incumbent is found.
