Honour Thy Neighbour: Clique Maintenance in Dynamic Graphs

Whenever objects and their interaction is modelled via undirected graphs, it is often of great interest to know the cliques of the graph. For several problems the graph changes frequently over time, and we therefore seek methods for updating the information about the cliques in a dynamic fashion to avoid expensive recomputations. This dynamic problem was investigated by Stix, and in this paper we derive a new simple method based on the Bron-Kerbosch algorithm that compares favourably to Stix’ approach. The new approach is generic in the sense that it can be used with other algorithms than just Bron-Kerbosch. The applications include fuzzy clustering and optimal triangulation of Bayesian networks.